How different are string matching and integer matching in terms of time complexity?
I'm asking this especially in relation to Rabin Karp algorithm. Why is it faster to compute a hash code for every substring and check for its equality with the hash code of the given search string than the naive method of just checking if any of the substrings match with the given string?
Typically, when designing algorithms, you assume that the machine model is such that any two integers (that fit into a machine word) can be compared in constant time. Since strings can be longer than a single machine word, comparing two strings of length n will require O(n) comparisons. Therefore, it's faster to compare two machine words than to compare two strings.
The Rabin-Karp algorithm is efficient because it uses comparisons of a hash code to minimize the number of times that expensive string comparisons are actually required. Specifically, Rabin-Karp only compares a substring against the pattern string if that substring has the same hash code as the original pattern string, which eliminates a lot of unnecessary work.
Hope this helps!
