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

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

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

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

Leave a Reply

Your email address will not be published. Required fields are marked *