![](https://codelido.com/assets/files/2022-11-30/1669809352-393817-image.png)
Example using alphabets
Text: A A B A A C B
Pattern: A A B A
Let q be any prime number and here consider q=23
Hash value of Pattern = (65+65+66+65)%23 = 8
Starting from 0th index in given Text
0 1 2 3 4 5 6
A A B A A C B
–>Taking Text[0] to Text[3]
(65+65+66+65)%23=8 ✓
As the hash value of considered part of text and pattern are matched, we will check both strings.
Text[0]==A
Text[1]==A
Text[2]==B
Text[3]==A
Both pattern characters and text characters are matched it is a VALID HIT found at 0th index.
Continuing the process,
0 1 2 3 4 5 6
A A B A A C B
–>Taking Text[1] to Text[4]
(65+66+65+65)%23 = 8 ✔
Text[1]==A
Text[2]==B
Text[3]==A
Text[4]==A
Not same so it is a spurious hit.
0 1 2 3 4 5 6
A A B A A C B
–>Taking Text[2] to Text[5]
(66+65+65+67)%23 = 10 !=8 ✗
As hash value is not same, move to next one
0 1 2 3 4 5 6
A A B A A C B
–>Taking Text[3] to Text[6]
(65+65+67+66)%23 = 10 !=8 ✗
We traversed upto n-m+1=4 elements where n(length of Text)=7 and m(length of Pattern)=4.
And in every iteration we have a chance of checking m elements at worst case.
Therefore the time complexity is O(n-m+1)m for worst case.
Best and average case time complexity occurs when taken prime number is large so that spurious hits will be avoided at maximum and if no of valid shifts are small.
Time Complexity Of Rabin-Karp Algorithm:
Worst Case: O(n-m+1)m
Average Case: O(n+m)
Best Case: O(n+m)