String Matching Algorithms Explained: Naive Search, KMP and Rabin-Karp

Sliding a pattern across a string is easy until KMP reuses a prefix after a mismatch or Rabin-Karp gives the same hash to two different windows. The difficulty is not finding one match; it is preserving useful work without skipping an occurrence. The main choices are naive search, KMP, and Rabin-Karp; KMP requires an exact LPS array and trace, while every rolling-hash hit requires verification.

1. The Pattern-Searching Problem and Its Vocabulary

Let the text T have length n and the pattern P have length m. A match at zero-based shift s means T[s + k] = P[k] for every 0 <= k < m. The valid shifts are 0 through n - m. If m > n, no match is possible. If the task asks for every occurrence, overlapping matches must be kept.

For T = ABABABA and P = ABA, matches begin at shifts 0, 2 and 4: T[0..2], T[2..4] and T[4..6] each equal ABA character by character. A left-to-right naive scan checks all five shifts and makes 11 character comparisons: three at each matching shift and one at each failing shift.

Naive search does no preprocessing and checks alignments directly. KMP preprocesses the pattern so a mismatch does not discard known structure. The earlier KMP and Rabin-Karp for GATE: The Failure Function and Rolling Hash, Fully Solved is the exam-focused pairwise walkthrough with ababaca and a two-digit rolling hash. Use the five-method comparison below when the constraint, overlap rule or exact comparison count determines the choice. The GATE CS Exam category connects these algorithms to the wider preparation sequence.

2. Which String-Matching Algorithm Should You Choose?

Choose naive search for tiny inputs, KMP for guaranteed linear search, Rabin-Karp for same-length hashes, Z for prefix lengths, and a Boyer-Moore variant for useful right-to-left skips. In Z, $ must be outside the alphabet; Boyer-Moore bounds vary by variant. Sorting Algorithms: Complexity and Comparison develops the related asymptotic comparisons.

3. Build the KMP LPS Array Without Guessing

For KMP, lps[k] is the longest proper prefix length of P[0..k] that is also a suffix. Proper means shorter than the whole substring. LPS is not a character, occurrence count or next text index.

Use P = ABABCABAB:

At index 4, C mismatches the candidate A. Fall from candidate length 2 to lps[1] = 0, then record 0. At index 8, the longest proper prefix and suffix is ABAB, so record 4.

During construction, i scans and len stores the candidate border length. On a match, increment both and store len. On a mismatch with len > 0, set len = lps[len - 1] without advancing i. When len = 0, record zero and advance.

4. Fully Worked KMP Search Trace

Search T = ABABDABACDABABCABAB, where n = 19, for P = ABABCABAB, where m = 9. Here i indexes the next text character and j the next pattern character.

Text indices 0..3 match ABAB. Next, T[4] = D mismatches P[4] = C. Keep i = 4 and fall through j: 4 -> lps[3] = 2 -> lps[1] = 0. The same D still mismatches P[0], so advance i to 5.

Text indices 5..7 match ABA, giving i = 8, j = 3. Now T[8] = C mismatches P[3] = B. Keep i = 8 and fall through j: 3 -> lps[2] = 1 -> lps[0] = 0. The C still mismatches P[0], so advance to i = 9. T[9] = D also mismatches P[0], so advance to 10.

Finally, T[10..18] = ABABCABAB matches all nine characters. Afterward, i = 19 and j = 9, so the start shift is i - j = 19 - 9 = 10. Counting every text-pattern comparison gives 23. This belongs only to this input and implementation; KMP does not always use fewer comparisons than naive search.

5. Why KMP Is Linear and How It Preserves Overlaps

Before each comparison, P[0..j-1] matches the suffix of T[0..i-1]. On a mismatch, lps[j-1] gives the longest shorter prefix that could remain that suffix. KMP changes j, never moving i backwards. Each iteration advances i or strictly decreases j. Search is O(n) after O(m) preprocessing, with O(m) space.

The trace shows 4 -> 2 -> 0 at i = 4 and 3 -> 1 -> 0 at i = 8. Some text positions are compared more than once, but the text pointer does not reverse.

For overlaps, take T = AAAAA, P = AAA, and lps = [0,1,2]. Matches start at 0, 1 and 2. After a full match, record i - m, then set j = lps[m - 1] = 2. Resetting j to zero discards the reusable border and can miss overlaps.

6. Rabin-Karp With Real Rolling-Hash Values

Take T = 31415926, P = 159, base d = 10, modulus q = 13, and m = 3. Digits use numeric values. Then h = d^(m-1) mod q = 10^2 mod 13 = 9, and the pattern hash is 159 mod 13 = 3.

Roll from 314, hash 2, by removing 3 and appending 1: t_next = (10 x (2 - 3 x 9) + 1) mod 13 = -249 mod 13 = 11. Code normalises negative remainders into 0..12; it does not rebuild each number.

At shift 3, hash 3 triggers verification; 159 = 159, so report a match. At shift 5, 926 mod 13 = 3, but 926 != 159, so reject the collision. Many such verifications produce the O(nm) worst case.

7. Constraint-Driven String-Matching Questions

Questions can ask you to construct an LPS array, find i and j after a mismatch, count comparisons for a stated implementation, retain overlaps, choose an algorithm under constraints, update a rolling hash, identify a collision or compare worst-case bounds. For these worked inputs, the check values are LPS ending in 4, KMP shift 10, overlap shifts 0, 1 and 2, pattern hash 3, and false hit 926.

Fix the implementation before counting comparisons, show every LPS fallback without moving i backwards, and verify every equal hash character by character. The GATE Test Series provides timed algorithm practice for applying that discipline.

8. Five Corrections and a Rebuild Drill

1. Define zero-based shifts and enumerate only 0 through n - m.

2. Store border lengths in LPS; a proper prefix is shorter than the complete substring.

3. On a mismatch, change j through LPS while keeping i on the same text character.

4. After a full match, set j = lps[m - 1] so overlapping occurrences remain visible.

5. Treat equal hashes as candidates, verify the characters, and include preprocessing in the total complexity.

Rebuild LPS = 0,0,1,2,0,1,2,3,4, trace the match at shift 10 and explain all 23 comparisons. Then recompute the six hashes and reject 926 after character verification. Continue with GATE Guidance by Sanchit Sir for the broader Algorithms sequence.