4
$\begingroup$

I asked a question on Rabin-Karp Searching algorithm here, which I am reading from the book "Introduction to Algorithms" 3rd edition Cormen et al..

After reading few para of the section on Rabin-Karp, I got some more confusions:

In the third paragraph the authors say that the if we could find p (decimal value of pattern P[1....m] ) in time O(m) and all the ts values (i.e decimal value of length-m sub-string T[s+1....s+m], s=0,1,2,,,,n-m) in time O(n-m+1), then we could determine all valid shifts s in time O(m) + O(n-m+1) by comparing p with each of the ts values.

How is this possible? O(m) is for finding p, O(n-m+1) is for finding all ts, so total pre-processing time so far is O(m) + O(n-m+1). This is the total pre-processing time; the comparison has yet to start, I have to spend some extra $ for doing comparison of a decimal p with each of the (n-m+1)-ts values.

1-Then why the authors say in the first para that the pre-processing time is O(m)? Why it is not O(m) + O(n-m+1) which include processing time of p and all ts values?

2- Now if we talk about worst case matching time, what should be that? So in the worst my decimal number p (already calculated ) will be compared with each of the another (m-n+1) decimal numbers, which are the values of ts (already calculated, no extra cash needed for doing this job now ). The worst case is when I am most unlucky and I have to compare every value of ts with p. Right?

Based on my understanding,(if I am right) the worst case matching time should be O(m-n+1) and not O((m-n+1)m) as claimed by the authors in the first para. For example let us say my Pattern is P[1...m]=226 and Text is T[1....n]=224225226. so my p is decimal 226, and ts is decimal value of T[s+1, s+2, s+3], for s=0,1,2...6 as n=9, and m=3. The ts values will be as follows:

s=0 => T[224]=> ts=224

s=1 => T[242]=> ts=242

s=2 => T[422]=> ts=422

s=3 => T[225]=> ts=225

s=4 => T[252]=> ts=252

s=5 => T[522]=> ts=522

s=6 => T[226]=> ts=226

Now you will be comparing p=226 with all these values. So are you not making n-m+1=7 comparisons to achieve search for 226 in T, and not (n-m+1)m =7 x3=21? So the worst case time should be O(n-m+1) and not O((n-m+1)m).

In short I understand that:

Total pre-processing time = O(m) + O(n-m+1) (including for both p and all the ts values)

Total matching time in worst case = O(n-m+1)

Where I am making mistake?

$\endgroup$
  • $\begingroup$ see the section on "rolling hash function" on wikipedia. can you rephrase this question terms of the rolling hash function and wikipedia pseudocode? also note wikipedias contrast of worst case vs average case complexity.... $\endgroup$ – vzn Mar 6 '13 at 16:11
6
$\begingroup$

As pointed out by vzn above, the wiki article has all the details you are looking for.

Firstly, what is pre-processing and what is the online runtime, depends on what is remaining constant and what is varying. For example, if we are given some fixed text and are asked to match various small strings with that text, pre-processing would be hashing the text.

In this case, let us say we have only one string to be compared with one text, to avoid confusion about pre-processing. The operations that we need to perform are

  1. Hash for string to be searched for ($p$) = $O(m)$
  2. Hash for each $m$-sized substring in the text ($T$) (assuming rolling hash) = $O(n-m+1)$
  3. Number of hash comparisons (one per each $m$ sized substring in $T$) = $O(n-m+1)$
  4. If there are $r$ matches in the hashes, then we compare each of those substrings of $T$ with $p$ (each comparison being $O(m)$) = $O(rm)$

But in worst case, the number of matches in hash can be as large as $n-m+1$. So worst case complexity will be $O(m(n-m+1))$.

$\endgroup$
  • $\begingroup$ I understand hash comes only when we have big numbers. The para that I have cited above from the book does not talk about hashing. It is only later it talks about hashing. $\endgroup$ – gpuguy Mar 8 '13 at 6:38
  • $\begingroup$ The process described in that highlighted para is an example of hashing. It says in the earlier para, that if we can match the decimal value of $p$ and $t_i$ in constant time, then the complexity is $O(n-m+1)$ as you wrote above. But these numbers can be too large to compare in constant time ($m$ could be large or the size of the alphabet set could be large). So we are reducing these numbers by taking modulo $q$. The numbers are smaller now, but the problem is two numbers are same modulo $q$ does not mean they are equal. So we need to explicitly compare strings which have equal modulus. $\endgroup$ – polkjh Mar 8 '13 at 7:56
-3
$\begingroup$
 /*   Pattern string length is m
 *   Source text length is n
 *   Find the index of the first matched substring in text
 *   Runtime:
 *
 *
 *      int hashOfPattern = hash(pattern string);           //  m.
 *      for(int i=0; i<= n-m; i++){                         //  n-m+1.
 *        int currentStringHash = hash(current substring);  //  1. using rolling hash method,
 *        if( currentStringHash == hashOfPattern){
 *           if(current substing equal to pattern string){
 *                                                          //  m. only execute once.
 *                                                          //  Assume it is an effective rolling hash method good enough
 *                                                          // to avoid hash collisions.
 *              return i;
 *           }
 *        }
 *      }
 *   In worse case the whole runtime is m + (n-m)*1 + 1*m = n+m
 *   it is O(n+m)
 *  
 *   If the hash function is not effective. The worse case runtime is O(nm).
 */
$\endgroup$
  • 4
    $\begingroup$ This doesn't address the asker's specific questions and it's also very hard to read: I have to scroll from side to side on my screen. Most of this is not code, so please don't format it as code. $\endgroup$ – David Richerby Oct 24 '16 at 7:47
  • 2
    $\begingroup$ The question is "where is my mistake" not "please copy an analysis here". Plus, what David wrote. $\endgroup$ – Raphael Oct 24 '16 at 11:15

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.