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=> ts=224
s=1 => T=> ts=242
s=2 => T=> ts=422
s=3 => T=> ts=225
s=4 => T=> ts=252
s=5 => T=> ts=522
s=6 => T=> 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?