Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

What's the worst case complexity for KMP when the goal is to find all occurrences of a certain string?

I would also like to know which algorithm has the worst case complexity of all for finding all occurrences of a string in another. Seems like Boyer–Moore's algorithm has a linear time complexity.

like image 791
Ouais Alsharif Avatar asked Feb 07 '12 19:02

Ouais Alsharif


People also ask

What is worst case running time of KMP algorithm?

If the length of W[] is k, then the worst-case performance is O(k⋅n). The KMP algorithm has a better worst-case performance than the straightforward algorithm.

What is the time complexity of string matching algorithm?

Time complexity O(m|Σ|) of this preprocessing (m = |x|, i.e.

What is the running time of the KMP algorithm if'n is the size of the input text and m is the size of the pattern?

Note that the sub-pattern starts at index 1 because a suffix can be the string itself. After a mismatched occurred at index P[j], we update j to F[j-1]. The original KMP Algorithm has the runtime complexity of O(M + N) and auxiliary space O(M), where N is the size of the input text and M is the size of the pattern.

What problem does the Knuth Morris Pratt algorithm solve?

The KMP algorithm is a solution to the string search problem wherein we are required to find if a given pattern string occurs in another main string. It is one of the advanced string matching algorithms that was conceived by Donald Knuth, James H.


1 Answers

The KMP algorithm has linear complexity for finding all occurrences of a pattern in a string, like the Boyer-Moore algorithm¹. If you try to find a pattern like "aaaaaa" in a string like "aaaaaaaaa", once you have the first complete match,

aaaaaaaaa
aaaaaa
 aaaaaa
      ^

the border table contains the information that the next longest possible match (corresponding to the widest border of the pattern) of a prefix of the pattern is just one character short (a complete match is equivalent to a mismatch one past the end of the pattern in this respect). Thus the pattern is moved one place further, and since from the border table it is known that all characters of the pattern except possibly the last match, the next comparison is between the last pattern character and the aligned text character. In this particular case (find occurrences of am in an), which is the worst case for the naive matching algorithm, the KMP algorithm compares each text character exactly once.

In each step, at least one of

  • the position of the text character compared
  • the position of the first character of the pattern with respect to the text

increases, and neither ever decreases. The position of the text character compared can increase at most length(text)-1 times, the position of the first pattern character can increase at most length(text) - length(pattern) times, so the algorithm takes at most 2*length(text) - length(pattern) - 1 steps.

The preprocessing (construction of the border table) takes at most 2*length(pattern) steps, thus the overall complexity is O(m+n) and no more m + 2*n steps are executed if m is the length of the pattern and n the length of the text.

¹ Note that the Boyer-Moore algorithm as commonly presented has a worst-case complexity of O(m*n) for periodic patterns and texts like am and an if all matches are required, because after a complete match,

aaaaaaaaa
aaaaaa
 aaaaaa
      ^
  <- <-
 ^

the entire pattern would be re-compared. To avoid that, you need to remember how long a prefix of the pattern still matches after the shift following a complete match and only compare the new characters.

like image 104
Daniel Fischer Avatar answered Sep 28 '22 07:09

Daniel Fischer