Computer scienceAlgorithms and Data StructuresAlgorithmsString algorithmsSubstring search algorithms

Rabin-Karp algorithm

The number of collisions

Report a typo

For a set of strings and a hash function h h , the number of collisions is the number of pairs of different strings with the same hash value for hh. Consider all substrings of length 3 of a string s=ACACBAD s = \textrm{ACACBAD} . How many collisions does the polynomial hash function with a=3a = 3 and m=11m = 11 have for all these substrings?

Enter a short text
___

Create a free account to access the full topic