Give an example of an input instance for lexicon matching pr

Give an example of an input instance for lexicon matching problem, with just a single pattern in the lexicon, L, that forces the Karp-Rabin algorithm given in Algorithm 23.11 to run in (nm) time.

Ps. String Algorithms

Solution

Answer

The Karp-Rabin algorithm has a runtime of (nm) time when all characters of pattern and text are same as the hash values of all the substrings of text match with hash value of pattern string.

So, when text string is like \"bbbbbbbbbbbbbb\" and pattern string is like \"bbb\" the Karp-Rabin algorithm run in (nm) time.