KMP and Rabin-Karp for GATE: The Failure Function and Rolling Hash, Fully Solved

String matching questions are usually won or lost in a small preprocessing table. If one KMP fallback is wrong, every later alignment can look plausible while the answer drifts away.

The cure is to define LPS precisely and compute it one comparison at a time. Rabin-Karp then supplies the second exam pattern: a rolling hash that is fast only because every hash hit is checked against the actual characters.

1. The setup: naive matching and its cost

Let text T have length n and pattern P have length m. The task is to find every starting index where the complete pattern occurs in the text.

Naive matching aligns P at a text position and compares characters. On a mismatch, it shifts the pattern by one and starts the comparison again. Previously checked text characters may therefore be checked repeatedly. The worst-case running time is O(n x m).

KMP prevents that repeated text work by using information about the pattern itself. Rabin-Karp computes a compact hash for each length-m text window and performs character comparison only when the window hash matches the pattern hash.

The algorithms save work in different ways:

• KMP: use prefix and suffix structure to choose a safe shift.

• Rabin-Karp: use a rolling hash to reject most windows cheaply.

2. The KMP failure function, or LPS array

For each pattern position i, lps[i] is the length of the longest proper prefix of P[0..i] that is also a suffix of P[0..i]. Proper means the prefix cannot be the whole substring.

Build the array from left to right. Maintain len, the length of the current candidate prefix, and start with lps[0] = 0.

1. If P[i] == P[len], increase len, store it in lps[i], and move to the next i.

2. If the characters differ and len > 0, set len = lps[len - 1] and compare again at the same i.

3. If they differ and len == 0, set lps[i] = 0 and move on.

The fallback does not guess a smaller length. It follows a previously computed LPS value. During matching, the same table tells KMP how much of the pattern prefix is already known to agree with the text suffix.

3. Fully worked example: LPS of ababaca

Take P = a b a b a c a, with indices 0 through 6.

Therefore:

lps = [0, 0, 1, 2, 3, 0, 1]

Check the difficult position directly. For ababac, possible non-empty proper prefixes are a, ab, aba, abab and ababa. None is also a suffix because the substring ends in c. Therefore lps[5] must be 0, which independently confirms the fallback calculation.

4. KMP matching run: find ababaca in abababacaba

Now use:

• T = a b a b a b a c a b a, indices 0 through 10

• P = a b a b a c a, length m = 7

• lps = [0, 0, 1, 2, 3, 0, 1]

Let i index the text and j index the pattern.

1. T[0..4] = ababa matches P[0..4] = ababa. The indices are now i = 5, j = 5.

2. Compare T[5] = b with P[5] = c. They differ.

3. Since j is not zero, set j = lps[j - 1] = lps[4] = 3. Keep i = 5.

4. Compare T[5] = b with P[3] = b. Match, so i = 6, j = 4.

5. T[6] = a matches P[4] = a, giving i = 7, j = 5.

6. T[7] = c matches P[5] = c, giving i = 8, j = 6.

7. T[8] = a matches P[6] = a, giving i = 9, j = 7.

Now j = m, so a full match has ended. Its starting index is:

i - m = 9 - 7 = 2

Direct verification gives T[2..8] = ababaca, exactly the pattern. The text index never moved backwards. The LPS value preserved the already useful suffix aba and avoided checking it again from the start.

5. Rabin-Karp: rolling hash and spurious hits

Rabin-Karp represents each length-m window in base d modulo a prime q. It compares the window hash with the pattern hash. Equal hashes make a window a candidate, not a confirmed match, because different strings can have the same remainder.

For a numeric example, take:

• pattern P = "26"

• text T = "31415926535"

• base d = 10

• modulus q = 11

The pattern hash is 26 mod 11 = 4. The text has ten windows of length 2:

There are exactly three spurious hits and one real match at index 6.

The rolling update is:

new = (d x (old - leading x d^(m - 1)) + incoming) mod q

For the first raw window value, move from 31 to 14:

1. Remove the leading digit: 31 - 3 x 10 = 1.

2. Shift the remaining digit left: 1 x 10 = 10.

3. Add the incoming digit: 10 + 4 = 14.

4. Reduce modulo 11: 14 mod 11 = 3.

The same idea updates each later window in constant time. Always normalise a negative modular result if the implementation language can return a negative remainder.

6. Complexity and how GATE tests this

KMP spends O(m) time building LPS and O(n) time scanning the text, for O(n + m) total time. Its control flow can fall back within the pattern, but the text index never backs up.

Rabin-Karp also preprocesses the pattern and scans the windows efficiently on average, giving O(n + m) average time in the standard analysis. Its worst case is O(n x m) when many windows share the hash and each candidate requires a full character check.

Typical questions ask you to compute an LPS array, trace a KMP shift, count spurious Rabin-Karp hits, apply one rolling update, or choose the correct complexity. Watch for two traps: omitting the word proper from the LPS definition, and treating every hash equality as a string match.

Our practice bank has over 1,100 questions on algorithms, covering string matching, hashing and complexity. Confirm the current Algorithms scope and any weightage detail on the official GATE portal for the relevant cycle.

7. The short version and your next step

KMP uses the LPS array to reuse a matched prefix without moving the text index back. Rabin-Karp rolls a hash to reject windows quickly, then verifies the characters because collisions create spurious hits. KMP is linear in the combined input size; Rabin-Karp is linear on average but can fall to O(n x m).

Connect the prefix-table habit to dynamic programming explained and the collision idea to hashing and collision resolution. Then build topic coverage with GATE Guidance by Sanchit Sir, practise under time pressure in the GATE Test Series, and use the GATE category for the wider path.