java - Partially match strings in case of List.contains(String)

Question

I have a List<String>

List<String> list = new ArrayList<String>();
list.add("ABCD");
list.add("EFGH");
list.add("IJ KL");
list.add("M NOP");
list.add("UVW X");

if I do list.contains("EFGH"), it returns true. Can I get a true in case of list.contains("IJ")? I mean, can I partially match strings to find if they exist in the list?

I have a list of 15000 strings. And I have to check about 10000 strings if they exist in the list. What could be some other (faster) way to do this?

Thanks.

Answer 1

If suggestion from Roadrunner-EX does not suffice then, I believe you are looking for Knuth–Morris–Pratt algorithm.

Time complexity:

• Time complexity of the table algorithm is O(n), preprocessing time
• Time complexity of the search algorithm is O(k)

So, the complexity of the overall algorithm is O(n + k).

• n = Size of the List
• k = length of pattern you are searching for

Normal Brute-Force will have time complexity of O(nm)

Moreover KMP algorithm will take same O(k) complexity for searching with same search string, on the other hand, it will be always O(km) for brute force approach.