Tuesday, 28 July 2020

Find Pattern And Its Anagrams In A Text

Previously I have written few posts related to pattern matching algorithms namely Rabin-Karp and KMP algorithms. So I thought of adding one layer of complexity on top of it. Now in addition to search a string, we need to find all its anagrams in the given text.
We can do it in O(n) time if we consider that character set in the given text would be of fixed length. For example, if we consider only English alphabet, we will have only 26 characters. You can check this link which explains it quite clearly. It uses Sliding Window technique. If you are familiar with it or have gone through Rabin-Karp Rolling Hash function already, then it is pretty easy to understand. Feel free to comment for any clarifications or if you have any other resource.

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...