java - Regex Optimization for large lists

Question

I am comparing two lists of strings to find possible matches. Example:

public class Tester {

    public static void main(String[] args) {

        List<String> test = new ArrayList<String>();
        List<String> test2 = new ArrayList<String>();

        test.add("3H0875AAAA0012");
        test.add("3H0875AABB0018");
        test.add("3H0875AAAC0010");
        test2.add("3H0875AA");


        for(String s2: test2){
            for (String s: test){
                if (s.matches(".*" + s2 + ".*")){
                    System.out.println("Match");
                }
            }
        }
    }
}

Basically for every string in test2 I want to see if there are any strings in test that contain test2 completely or partially. The output for the above code should be:

Match 
Match 
Match

However, in my real case scenario I have around 225K strings in test and around 5K strings in test2. It is taking too long process this comparison and wanted to see if it was possible to optimize the comparison. It takes about 10 minutes to analyze the first 1.5K items in test2. So it will take at least 30 to 40 minutes to finish the comparison.

Thanks in advance

Answer 1

I think that you shouldn't use regex for that: I believe that looking into String#contains (here is a link to its javadoc entry) would give you better results, in terms of performance ;)

For example, your code could be:

for(final String s2: test2){
    for (final String s: test){
        if(s.contains(s2)) {
            System.out.println("Match");
        }
    }
}