Trace the Rabin-Karp search algorithm on pattern “ccc” and text “dccdcddccddcccd” using the fingerprint function in Fig. 5.81 with q = 5. The ASCII code for the letters ’c’ and ’d’ are 99 and 100 respectively. Show the value of the fingerprint at each position in the text and mark the positions where there is a match with the fingerprint of the pattern. How many comparisons between the pattern and text characters are done?

 

int fingerprint (char str [], int m, const int q) { } } int i, finger; for (i = 0, finger 0; i