String matching

Question 1

Describe brute force string matching, with some string S and some pattern P.

Answer 1

Try matching each substring in S against P.

S = AAAB
P = AB

i = 0
AAAB
AB

i = 1
AAAB
_AB

i = 2
AAAB
__AB -> Match!

Code:
for (int i = 0; i < M.length - P.length; i++) {
\_\_ int j = -1;
\_\_ while (++j < P.length) {
\_\_\_\_ if (S[i+j] != P[j]) break;
\_\_}
\_\_ if (j == P.length) return true;
}

return false;

Question 2

Describe the Rabin-Karp string matching method, with some string S and pattern P.

Answer 2

Try creating a cheap hash of the pattern you want to match, then create that hash for each substring you want to check.

The trick comes in making the hash cheap, eg. the additive value of all the letters. When you advance the substring in S, subtract (evict) the leftmost character and add the rightmost.

P_h = hash(P, 0, P.length);
for (int i = 0; i < M.length - P.length; i++) {
\_\_ S_h = hash(P, 0, P.length);
\_\_ if (S_h == P_h) {
\_\_\_\_ int j = 0;
\_\_\_\_ while (++j < P.length) {
\_\_\_\_\_\_ if (S[i+j] != P[j]) break;
\_\_\_\_ }
\_\_\_\_ if (j == P.length) return true;
\_\_ }
}

return false;