[Solved]: string matching vs integer matching

Problem Detail: 

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 hash code for every substring and check for equality of hashcode with the hashcode of the given string than the naive method of just checking if amy of the substrings match with the given string?

Asked By : codeln

Answered By : D.W.

Checking whether two 32-bit integers are equal can be done in a single machine instruction.

Checking whether two strings are equal can take a lot longer. If my two strings are each 100 characters long, then checking whether those two strings are equal might require the equivalent of about 100 machine instructions: I have to check them, character by character.

In asymptotic complexity terms: checking equality of (fixed-precision) integers takes $O(1)$ time, checking equality of strings takes $O(n)$, where $n$ denotes the length of each string.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/22480

3.2K people like this

 Download Related Notes/Documents