1
$\begingroup$

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 $\mathcal{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 $\mathcal{O}(nm)$?

$\endgroup$
4
  • 2
    $\begingroup$ Are you looking for multiple string pattern matching algorithms? If so, you can check and start from the Rabin–Karp algorithm (wiki): For text of length $n$ and $p$ patterns of combined length $m$, its average and best case running time is $O(n+m)$ in space $O(p)$, but its worst-case time is $O(nm)$. $\endgroup$
    – hengxin
    Commented Jan 20, 2015 at 14:43
  • $\begingroup$ Yes this was the algorihm i came up with myself, i where just wondering if there where anything faster :D But it dose not seem like it $\endgroup$
    – Androme
    Commented Jan 20, 2015 at 15:05
  • 1
    $\begingroup$ If the searched strings (many queries) or the strings sought (many searched strings) are repeatedly used, some preprocessing might be justified. E.g., > "dog" could filter mismatches for {"dog","cat","apple"} (if searched strings were preprocessed false possible matches from ' ' being < 'd' could be avoided). Practically, branch prediction, cache behavior, and SIMD might be more important than theoretical big-O (especially if based on character comparison count). $\endgroup$
    – user4577
    Commented Jan 23, 2015 at 5:12
  • $\begingroup$ @PaulA.Clayton Very good idea! I will have many match pattern 1000+ but they do not change during the lifetime of the application. $\endgroup$
    – Androme
    Commented Jan 26, 2015 at 9:58

3 Answers 3

3
$\begingroup$

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)$.

$\endgroup$
2
  • $\begingroup$ Thank you! Knuth-Morris-Pratt string matching, seems like something i can be using. Just a note, i am interested in what patterns are matches, i am just not interested in how many times each pattern are matches. $\endgroup$
    – Androme
    Commented Jan 21, 2015 at 9:41
  • $\begingroup$ Liked I said, you can modify to once a match was found, just break the loop, that will make your search even more faster! $\endgroup$
    – H_DANILO
    Commented Jan 21, 2015 at 12:25
2
$\begingroup$

If you are interested in the fastest way, then KMP is NOT the way to go, because what happens is that you have $K$ patterns you have to pre-compute and later search for each of them starting from the beginning. Also note that some pattern may overlap some other pattern which KMP does not utilize. Obviously, if you have $K$ patterns (each of length $N$) and a text of length $M$, then your time complexity is $\mathcal{O}(KM)$ for the search and $\mathcal{O}(KN)$ for preprocessing.

However, you can do better by utilizing the relationship between the patterns. You can use the Aho-Corasick data structure which is exactly what you are searching for.

Preprocessing time: $\mathcal{O}(KN)$
Searching: $\mathcal{O}(M)$

In general, the construction is very similar to McCreight's suffix tree construction where suffix links are utilized to make building the suffix tree fast enough.

What I would suggest is to implement a naive construction of the Aho-Corasick automata and then write the search function. Later modify the construction to the fast one where suffix links are used.

P.S.
If you are to use an algorithm like KMP which is rather naive for the multiple string matching problem, you are better off using Crochemore's pattern matching algorithms since it doesn't use any extra space.

$\endgroup$
0
$\begingroup$

As a worst case, consider string abc...xyz and patterns z, yz, xyz,...

I think you can't do better than $\mathcal{O}(np)$, with $p$ number of patterns.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.