Log inSign up
hardgeeksforgeeksNot Started

KMP Pattern Matching

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Strings
Solve on geeksforgeeks
Lesson

Problem Statement

Given two strings, one is a text string txt and the other is a pattern string pat. The task is to find all the starting indices (0-based) where the pattern pat appears as a substring in txt.

Return the list of all such 0-based starting indices in increasing order. If the pattern does not appear in the text, return an empty list.

Example 1 · Example:

Input: txt = "ababcabcabababd", pat = "ababd"
Output: [10]
Explanation: The pattern "ababd" appears only once in the text starting at 0-based index 10.

Example 2 · Example:

Input: txt = "aaaaa", pat = "aaa"
Output: [0, 1, 2]
Explanation: The pattern "aaa" appears at indices 0, 1, and 2 in "aaaaa".

Example 3 · Example:

Input: txt = "batmanandrobin", pat = "superman"
Output: []
Explanation: The pattern does not appear in the text.

Constraints:

  • 1 <= txt.length, pat.length <= 105
  • txt and pat consist of lowercase English alphabets.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master LPS table generation in O(M) time and space.
  • Implement the linear KMP pattern search loop.
  • Handle multi-occurrence and overlapping matches correctly.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Linear time exact substring search across massive text strings.
  • Finding all overlapping or non-overlapping pattern occurrences.
  • Finding periodic or repeating string prefixes.

Algorithmic Decision Tree:

  • Longest Prefix Suffix (LPS) Precomputation
  • Deterministic Finite Automaton on Strings

Connected Patterns:

Longest Prefix SuffixRepeated Substring PatternImplement strStrRabin Karp Pattern Matching

1. Naive Window Sliding (Quadratic Check)

Intuition

For every index i from 0 to n - m, compare characters txt[i + j] and pat[j] for j from 0 to m - 1. If all m characters match, append i to results. If a mismatch occurs, increment i by 1 and start over.

When to apply: Basic baseline comparison.

Algorithm

  1. Initialize res = [].
  2. Loop i from 0 to n - m:
  3. For j from 0 to m - 1:
  4. If txt[i + j] != pat[j]: break.
  5. If j == m: append i to res.
  6. Return res.

Interactive Trace

2 of 2 questions left today
Step 1 / 5
Trace timeline20% explored
Current operationSTEP 1 OF 5
Compute LPS for "aaa": lps = [0, 1, 2]
Visual state
Values and pointers at this exact step
pointers
S
a
b
a
b
c
a
b
c
a
b
a
b
a
b
d
0
↑ i
1
2
3
4
5
6
7
8
9
10
11
12
13
14
Check / comparison
lps: [0, 1, 2]
Decision / next transition
Advance to next character/state.
Why this step matters

Compute LPS for "aaa": lps = [0, 1, 2].

Step 1 / 5
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4
5class Solution {
6public:
7 std::vector<int> search(std::string pat, std::string txt) {
8 std::vector<int> res;
9 int n = txt.size(), m = pat.size();
10 if (n < m) return res;
11
12 for (int i = 0; i <= n - m; ++i) {
13 int j = 0;
14 while (j < m && txt[i + j] == pat[j]) {
15 j++;
16 }
17 if (j == m) {
18 res.push_back(i);
19 }
20 }
21 return res;
22 }
23};
24
25int main() {
26 Solution sol;
27 auto ans = sol.search("aaa", "aaaaa");
28 for (int x : ans) std::cout << x << " "; // 0 1 2
29 std::cout << std::endl;
30 return 0;
31}

Time & Space Complexity

  • Time complexity: O((N - M + 1) * M) — Up to N - M + 1 positions check up to M characters.
  • Space complexity: O(1) extra space

Why Brute Force Doesn't Scale:

Guarantees strictly O(N + M) runtime in all scenarios, avoiding the O(N * M) worst-case trap.

Only uses an integer array of size M.

2. Rabin-Karp Rolling Hash Matching

Intuition

Compute hash of pat and the first m characters of txt using polynomial base B and large prime MOD. Slide the window: subtract outgoing character's high-order contribution, multiply by base, and add incoming character. When hashes match, verify characters to eliminate false-positive collisions.

When to apply: When searching for patterns in stream or searching multiple patterns simultaneously.

Algorithm

  1. Compute initial polynomial hashes pHash and tHash.
  2. Precalculate h = (B^(m-1)) % MOD.
  3. Loop i from 0 to n - m:
  4. If pHash == tHash and txt.substr(i, m) == pat: add i to result.
  5. Update tHash for next window i + 1 by sliding.
  6. Return result.

Interactive Trace

2 of 2 questions left today
Step 1 / 5
Trace timeline20% explored
Current operationSTEP 1 OF 5
Compute LPS for "aaa": lps = [0, 1, 2]
Visual state
Values and pointers at this exact step
pointers
S
a
b
a
b
c
a
b
c
a
b
a
b
a
b
d
0
↑ i
1
2
3
4
5
6
7
8
9
10
11
12
13
14
Check / comparison
lps: [0, 1, 2]
Decision / next transition
Advance to next character/state.
Why this step matters

Compute LPS for "aaa": lps = [0, 1, 2].

Step 1 / 5
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4
5class Solution {
6public:
7 std::vector<int> search(std::string pat, std::string txt) {
8 std::vector<int> res;
9 int n = txt.size(), m = pat.size();
10 if (n < m) return res;
11
12 long long d = 256, q = 1000000007;
13 long long p = 0, t = 0, h = 1;
14
15 for (int i = 0; i < m - 1; i++)
16 h = (h * d) % q;
17
18 for (int i = 0; i < m; i++) {
19 p = (d * p + pat[i]) % q;
20 t = (d * t + txt[i]) % q;
21 }
22
23 for (int i = 0; i <= n - m; i++) {
24 if (p == t) {
25 bool match = true;
26 for (int j = 0; j < m; j++) {
27 if (txt[i + j] != pat[j]) {
28 match = false;
29 break;
30 }
31 }
32 if (match) res.push_back(i);
33 }
34 if (i < n - m) {
35 t = (d * (t - txt[i] * h) + txt[i + m]) % q;
36 if (t < 0) t += q;
37 }
38 }
39 return res;
40 }
41};
42
43int main() {
44 Solution sol;
45 auto ans = sol.search("ababd", "ababcabcabababd");
46 for (int x : ans) std::cout << x << " "; // 10
47 std::cout << std::endl;
48 return 0;
49}

Time & Space Complexity

  • Time complexity: O(N + M) average, O(N * M) worst case — Rolling hash update is O(1) per step. Collisions trigger character verification.
  • Space complexity: O(1) extra space

3. Knuth-Morris-Pratt (KMP) with LPS Table

Intuition

Precompute the LPS array for pattern pat. Initialize text index i = 0 and pattern index j = 0. Whenever txt[i] == pat[j], increment both i and j. If j == m, we found a full match at i - m, record it and set j = lps[j - 1]. If mismatch occurs: if j > 0, set j = lps[j - 1] without changing i; if j == 0, increment i++.

When to apply: The standard optimal deterministic linear-time algorithm for exact pattern search.

Algorithm

  1. Compute lps array of size m for pattern pat.
  2. Initialize res = [], i = 0, j = 0.
  3. While i < n:
  4. If txt[i] == pat[j]: i++, j++.
  5. If j == m:
  6. res.push(i - m)
  7. j = lps[j - 1]
  8. Else if i < n and txt[i] != pat[j]:
  9. If j > 0: j = lps[j - 1].
  10. Else: i++.
  11. Return res.

Knuth-Morris-Pratt Fallback Automaton Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [A, B, A, B, D, A, B, A, C]
Current operationSTEP 1 OF 6
Observation: Precompute LPS table for pat = "ABABCABAB"
Visual state
Values and pointers at this exact step
array
S
A
B
A
B
D
0
↑ i=0: compare prefix
1
2
3
4
Variables at this step
lps
[0,0,1,2,0,1,2,3,4]
i
4
j
4
matchedPrefix
ABAB
Why this step matters

Observation: Precompute LPS table for pat = "ABABCABAB". Matches progress through txt[0..3] = "ABAB" with j = 4.

Decision: Continue forward to index 4.

Invariant: LPS array memoizes longest prefix-suffix overlaps.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4
5class Solution {
6 std::vector<int> computeLPS(const std::string& pat) {
7 int m = pat.size();
8 std::vector<int> lps(m, 0);
9 int len = 0, i = 1;
10 while (i < m) {
11 if (pat[i] == pat[len]) {
12 len++;
13 lps[i] = len;
14 i++;
15 } else {
16 if (len != 0) {
17 len = lps[len - 1];
18 } else {
19 lps[i] = 0;
20 i++;
21 }
22 }
23 }
24 return lps;
25 }
26public:
27 std::vector<int> search(std::string pat, std::string txt) {
28 std::vector<int> res;
29 int n = txt.size(), m = pat.size();
30 if (m == 0 || n < m) return res;
31
32 std::vector<int> lps = computeLPS(pat);
33 int i = 0, j = 0;
34
35 while (i < n) {
36 if (txt[i] == pat[j]) {
37 i++;
38 j++;
39 }
40 if (j == m) {
41 res.push_back(i - m);
42 j = lps[j - 1]; // Continue search for overlapping occurrences
43 } else if (i < n && txt[i] != pat[j]) {
44 if (j != 0) {
45 j = lps[j - 1];
46 } else {
47 i++;
48 }
49 }
50 }
51 return res;
52 }
53};
54
55int main() {
56 Solution sol;
57 auto ans1 = sol.search("ababd", "ababcabcabababd");
58 for (int x : ans1) std::cout << x << " "; // 10
59 std::cout << std::endl;
60
61 auto ans2 = sol.search("aaa", "aaaaa");
62 for (int x : ans2) std::cout << x << " "; // 0 1 2
63 std::cout << std::endl;
64 return 0;
65}

Time & Space Complexity

  • Time complexity: O(N + M) strictly — Preprocessing pat takes O(M) time and space. Scanning txt takes O(N) operations without backtracking i.
  • Space complexity: O(M) for LPS array

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Naive Quadratic SearchO((N - M + 1) * M)O(1)Extremely simple code.Suffers O(N * M) worst case on repetitive patterns (e.g., txt=aaaa..., pat=aaab).
2.Rabin-Karp Rolling HashO(N + M) average, O(N * M) worst caseO(1)Great for multiple pattern searches.Susceptible to hash collisions in adversarial cases.
3.Knuth-Morris-Pratt (KMP)OptimalO(N + M) strictlyO(M) for LPS arrayDeterministic linear worst-case time, zero backtracking of input stream.Requires understanding the LPS table generation.

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Resetting j to 0 instead of lps[j - 1] after finding a match, missing overlapping occurrences.

Pitfall 2:

Incrementing i when falling back j on mismatch (i must remain stationary).

Crucial Edge Cases to Validate:

  • Pattern length > Text length: Returns empty list immediately.
  • Overlapping pattern occurrences (e.g., txt=aaaaa, pat=aaa): Setting j = lps[j - 1] upon full match correctly preserves prefix overlap to find all start indices [0, 1, 2].
  • Pattern not found: Returns empty list [].

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Clearly define what LPS stands for (Longest Proper Prefix which is also a Suffix).
  2. Explain that the text pointer i only moves forward, guaranteeing linear time complexity.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What does setting j = lps[j - 1] accomplish when a match or mismatch occurs?

Back to DSA Sheet