What is the difference between KMP and Z algorithm of string pattern matching?

user_15784904 0
Viewed 497

In KMP algorithm we preprocess the pattern to find the longest prefix which we used to skip characters while matching.

while in Z- algorithm we first make a new string
new_string = pattern + 'x' + string
where x = character that doesn't exist in both pattern and string
After making the new_string we preprocess the new_string to find longest prefix and if the lent of prefix is equal to pattern length then we found the pattern

Both have time complexity of O(m+n).

so what is the difference between these two algorithms and which one is best to use?

matching algorithm string
1 Answers

Is not always about time complexity, the storage complexity are the playing role here:

Knuth Morris Pratt:

Worst-case performance : Θ(m) preprocessing + Θ(n) matching

Worst-case space complexity : Θ(m)

Z algorithm:

Worst-case performance: Θ(m+n) preprocessing and matching

worst-case space complexity: Θ(n+m)

Besides, you can use the idea of searching prefix and suffix for other usages beside searching a pattern, so you could have other reasons to do the analytics on particular information

Also I would recommend for other matching algorithms for some tasks even if they have worse time complexity like Boyer-moore, it all depend on the situation

user_153252950
Related