Pattern Matching Algorithm

Suppose we need to find if some text contains a pattern or any of its anagrams. I will explain how you can do it in O(n) time. Let’s consider the example below: Text: cedaabd Pattern: abad Here are all possible 4-letter anagrams of abad: aabd aadb abad abda adab adba baad bada bdaa daab daba … Read more

Here I am just trying to explain KMP algorithm in plain english. I will also explain worst time complexity & why it is O(m + n). We will take two examples, one with no repeatable character in the pattern & another with repeatable characters in the pattern. Text:    aaaabaabab Pattern: aaaaa First, we need … Read more

In this post, I will try to explain Rabin-Karp Algorithm & its worst time complexity. Rabin-Karp pattern matching algorithm is based on hash matching. Let’s take an example. Text:    aadabc Pattern: abc We will use a simple hash function. Lets create a table as below: a b c d e 1 2 3 4 … Read more