0
$\begingroup$

I'm trying to determine the input for the worst case time complexity of Karb-Rabin regardless of the used hash function. However, I'm seeing both of these answers on the Internet:

  • String "AAAAAAAA" and pattern "AAA"

  • String "AAAAAAAB" and pattern "AAB"

Which of these inputs would have the worst running time in Karp-Rabin? Or are they both providing the worst case running time? Thanks!

$\endgroup$
2
$\begingroup$

It all depends on what hash function you are using for your strings. The worst case for Rabin-Karp would be a case in which every single substring of the text has an equal hash to the pattern, therefore every single substring would be compared and the algorithm is equivalent to brute force.

The first example would be an example of this since the pattern matches in every case, therefore the algorithm would have to individually compare every substring (Assuming you are looking for every match and don't break out on the first one).

The second example would only be an example of a worst case if the hash of "AAB" matches the hash of "AAA," which is unlikely unless you have a really bad hash function. The algorithm would compare the hash of each substring of "AAA" and "AAB" and determine them to be non equal and bypass them until reaching the end where it hits "AAB" and finds and equal hash, comparing the substrings and determining them to be equal.

$\endgroup$
  • $\begingroup$ Thanks, so basically regardless of the used hash function, the worst case is a string with the most occurrences of the pattern, therefore the first example. Am I getting it right? $\endgroup$ – james F. May 22 at 13:17
  • $\begingroup$ Yes, cases where the hash matches a lot is the worst case for Rabin-Karp. Obviously cases where the pattern matches would have a matching hash, so that would be an example. $\endgroup$ – Michael Moschella May 22 at 13:41
0
$\begingroup$

Worst case for Rabin-Karp string search is hash collision, i.e when you look for "ABCD" and other string "XXXX" has the same length and hash, and then the text consists purely of 'X' chars :)

$\endgroup$
  • $\begingroup$ So basically the first case, since the hash codes match? $\endgroup$ – james F. May 22 at 13:18
  • $\begingroup$ do you know the algorithm at all? it seems that you just don't got the explanation $\endgroup$ – Bulat May 22 at 13:39
  • $\begingroup$ What I didn't get? I understand that hash collision or matching hash means worst case, and since there are n collisions in the first example, it would be the worst case? $\endgroup$ – james F. May 22 at 13:43
  • $\begingroup$ 1) the main point of you question is "regardless of hash function". the second case is worst one for another string search algo $\endgroup$ – Bulat May 22 at 13:50
  • $\begingroup$ 2) you don't specified whether you need to find all occurences or the first one which makes answer impossible $\endgroup$ – Bulat May 22 at 13:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.