I am trying to speed up one of my application, one of the places where I can spe

Question

I am trying to speed up one of my application, one of the places where I can speed up is in my test if a string contains an array of strings.

example: I have the matches "dog", "cat" "apple" and the string "The dog chases the cat".

In this example would I like an algorithm that returns "dog" and "cat". I do not care, how many times, or where in the string it is, I just want to know what of my matches exists.

The fastest algorithm i can think of for this is O(nm) where n is the length of the string, and m is the count of matches.

But my question is are there an algorithm out there, there can do this faster then O(nm)?

Explanation / Answer

You can do that using Knuth/Moris/Pratt(kmp), the build table portion of algorithm is O(m) and the search part is O(n), being n the size of text and m the size of the pattern, to be more accurate, if you have 3 potential pattern, you'll do that in 3?O(n+m), because you'll probably have to search it 3 times and build 3 tables.

As you problem is about having the pattern or not, once you find one, you can break the loop and that ofc counts as an optimization. If the pattern are static, by this I mean, they probably are always the same, you may store the prefix-table content of each pattern and that will make O(m) one time, next time it'll just be O(n).

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.