3

I've been trying to solve the following problem in CLRS:

How can you extend the Rabin-Karp method to find k different patterns in a given text at once? At first assume all patterns have same length, then generalize to allow different length string patterns.

The easier case can be done by using a HashSet - by throwing hash of k patterns into it, and then using one pass through a given world, we can check in O(1) time, if the current hash is in the HashSet.

I'm wondering about generalizing it however. The best approach I found requires j passes through a text, where j is number of different pattern lengths (one pass for each length).

Can it be done better? I'm looking for a linear time solution (O(n+m) where m is size of all k patterns combined).

I saw Using Rabin-Karp to search for multiple patterns in a string, but there is no answer for different length patterns.

Community
  • 1
  • 1
qiubit
  • 4,708
  • 6
  • 23
  • 37
  • The only thing I could imagine is taking the minimum length of all patterns in the case where they are not too different in length. But you won't get any worst-case guarantees with that approach – Niklas B. Feb 06 '16 at 10:09

0 Answers0