Show the comparisons the Rabin-Karp String matching algorithm makes for the pattern P in the string S
Show the comparisons the Rabin-Karp String matching
string S. Here S is given as below:
JSFTVCHBAGHAACAAIAABAAJAAAGAADAAFAAEAADE
And pattern P is XAA where X is the letter equivalent to the (total of your Roll#) mod 10. Use
the given table for equivalency.
0 1 2 3 4 5 6 7 8 9
A B C D E F G H I J
Hint: If the roll# is 2018-CS-276 then take 276, add three digits i.e. 2+7+6=15, take (15 mod 10)
= 5 and in table 5 is F, so your pattern would be FAA.
Tasks:
1. Apply the RK algorithm and return the location of S if pattern P is found in S.
2. Calculate the Hash value using hash function.
3. Also count the spurious hits.
4. Define the time complexity of the algorithm
Trending now
This is a popular solution!
Step by step
Solved in 4 steps
