Monday, 27 July 2020

KMP Algorithm Explained In Plain English

As I covered Rabin-Karp algorithm in my previous post, I just remembered one detailed explanation that I read quite a while back regarding KMP algorithm. As KMP is also a part of string searching algorithms, I thought of sharing that article here. I have seen other resources or articles with good enough explanations. But if you are new to pattern matching algorithm or confused about how KMP algorithm works, then you should consider reading this. Especially how you create a proper prefix (which is also a suffix) table and then use it to skip through the characters has been explained in details. There might be few typos here & there, but it is a good place to start for beginners. Just check the comments section for the typos mentioned.
P.S. I saw some abusing comments to a particular comment in that article 😕. Just skim through that.

No comments:

Post a comment

Direct Conversion From Any Number Base To Another Base Explained

Let's consider that we need to convert a base 4 number to base 8 number. Base 4 digits: 0 1 2 3 Base 8 digits: 0 1 2 3 4 5 6 7 We should...