KMP and string matching interview questions with solutions
Last updated 2026-11-19
Finding a pattern inside a text looks simple until you notice the naive method restarts from scratch after every mismatch, which costs O(n * m) on inputs such as "aaaa...ab" searched in "aaaa...a". The Knuth-Morris-Pratt (KMP) algorithm avoids this by precomputing, for each prefix of the pattern, the length of its longest proper prefix that is also a suffix. After a mismatch it jumps back using that table instead of re-reading the text.
This page works from the plain search through the prefix function (also called the LPS array or failure function), and uses it to solve a family of problems: repeated patterns, happy prefixes and shortest palindromes. It also covers Rabin-Karp hashing and the Z-function as alternatives. For general string handling see string questions, and for the sliding window view of substrings see sliding window questions.
| Problems | 10, easy to hard |
|---|---|
| Languages | Python and Java |
| Core tool | Prefix function (LPS array) |
The prefix function in plain words
For a pattern p, lps[i] is the length of the longest proper prefix of p[0..i] that is also a suffix of p[0..i]. For "ababaca" the table is 0, 0, 1, 2, 3, 0, 1. When matching fails after k characters matched, the next candidate is lps[k - 1]: those characters of the pattern are already known to match the text, so there is no need to compare them again.
The text pointer never moves backwards. Each step either advances the text pointer or reduces k, and k can only rise as fast as the text pointer moves, so the total work is O(n + m).
- Build lps in O(m) with the same fallback logic.
- Search in O(n) using lps to fall back on mismatch.
- The last lps value of a string is its longest prefix that is also a suffix.
- If n - lps[n - 1] divides n, the string is a repeated block.
When to choose which method
Use the library find for ordinary cases (Python in, Java indexOf). Use KMP when the interviewer asks for linear guarantees or when the question is really about prefixes and suffixes. Use Rabin-Karp for searching many patterns of the same length or for comparing substrings through hashes. Use the Z-function when you need the common prefix length at every position.
KMP and string matching interview questions with solutions: questions with worked answers
1 Implement strStr: return the index of the first occurrence of a needle in a haystack, or -1.
easyThe straightforward method tries every starting position and compares the next m characters, stopping on the first mismatch. An empty needle returns 0 by convention. It is simple and fast enough on typical inputs, but quadratic in the worst case, which motivates KMP. Time O(n * m) worst case, space O(1).. Edge cases: empty needle (0), needle longer than the haystack (-1), match at the very end.
pythondef str_str(hay, needle): n, m = len(hay), len(needle) for i in range(n - m + 1): if hay[i:i + m] == needle: return i return -1javaimport java.util.*; class Solution { static int strStr(String hay, String needle) { int n = hay.length(), m = needle.length(); for (int i = 0; i + m <= n; i++) if (hay.startsWith(needle, i)) return i; return -1; } }2 Build the KMP prefix function (LPS array) for a pattern.
mediumKeep k, the length of the current matched prefix. For each position i from 1, while k is positive and p[i] differs from p[k], fall back to lps[k - 1]. If p[i] equals p[k], increase k. Store lps[i] = k. The fallback is the same idea as in searching, and the amortised cost is linear. Time O(m), space O(m).. Edge cases: single character (0), all identical characters (0, 1, 2, ...), no repeats.
pythondef build_lps(p): lps = [0] * len(p) k = 0 for i in range(1, len(p)): while k and p[i] != p[k]: k = lps[k - 1] if p[i] == p[k]: k += 1 lps[i] = k return lpsjavaimport java.util.*; class Solution { static int[] buildLps(String p) { int[] lps = new int[p.length()]; int k = 0; for (int i = 1; i < p.length(); i++) { while (k > 0 && p.charAt(i) != p.charAt(k)) k = lps[k - 1]; if (p.charAt(i) == p.charAt(k)) k++; lps[i] = k; } return lps; } }3 Search for a pattern in a text with KMP and return the first match index.
mediumWalk the text with a pointer i and keep k, the number of pattern characters currently matched. On a mismatch, fall back with k = lps[k - 1] without moving i. On a match, increase k. When k equals the pattern length, the match starts at i - k + 1. The text pointer never goes backwards. Time O(n + m), space O(m).. Edge cases: empty pattern (0), pattern longer than the text, overlapping candidates such as "aab" in "aaab".
pythondef kmp_search(s, p): if not p: return 0 lps = build_lps(p) k = 0 for i, ch in enumerate(s): while k and ch != p[k]: k = lps[k - 1] if ch == p[k]: k += 1 if k == len(p): return i - k + 1 return -1javaimport java.util.*; class Solution { static int kmpSearch(String s, String p) { if (p.isEmpty()) return 0; int[] lps = buildLps(p); int k = 0; for (int i = 0; i < s.length(); i++) { while (k > 0 && s.charAt(i) != p.charAt(k)) k = lps[k - 1]; if (s.charAt(i) == p.charAt(k)) k++; if (k == p.length()) return i - k + 1; } return -1; } // buildLps is the method from the previous problem }4 Find every occurrence of a pattern in a text, including overlapping ones.
mediumRun the same KMP loop, but after recording a match at i - k + 1, set k = lps[k - 1] instead of stopping. That reuses the longest border of the matched pattern, so overlapping matches such as "aa" in "aaaa" (positions 0, 1, 2) are all found without restarting. Time O(n + m), space O(m + number of matches).. Edge cases: overlapping matches, no matches (empty list), pattern equal to the text.
pythondef kmp_all(s, p): if not p: return [] lps = build_lps(p) res, k = [], 0 for i, ch in enumerate(s): while k and ch != p[k]: k = lps[k - 1] if ch == p[k]: k += 1 if k == len(p): res.append(i - k + 1) k = lps[k - 1] return resjavaimport java.util.*; class Solution { static List<Integer> kmpAll(String s, String p) { List<Integer> res = new ArrayList<>(); if (p.isEmpty()) return res; int[] lps = buildLps(p); int k = 0; for (int i = 0; i < s.length(); i++) { while (k > 0 && s.charAt(i) != p.charAt(k)) k = lps[k - 1]; if (s.charAt(i) == p.charAt(k)) k++; if (k == p.length()) { res.add(i - k + 1); k = lps[k - 1]; } } return res; } // buildLps is the method from the LPS problem }5 Longest happy prefix: the longest non-empty proper prefix of s that is also a suffix.
mediumThat is exactly the last value of the prefix function. Build lps for s and take s[:lps[-1]]. For "level" the answer is "l"; for "ababab" it is "abab". Time O(n), space O(n).. Edge cases: no border (empty string result), a single character, all characters equal ("aaa" gives "aa").
pythondef longest_prefix(s): if not s: return "" return s[:build_lps(s)[-1]]javaimport java.util.*; class Solution { static String longestPrefix(String s) { if (s.isEmpty()) return ""; int[] lps = buildLps(s); return s.substring(0, lps[s.length() - 1]); } // buildLps is the method from the LPS problem }6 Repeated substring pattern: can a string be built by repeating a smaller block?
mediumLet n be the length and b = lps[n - 1] the longest border. The shortest repeating block would have length n - b. The string is a repetition exactly when b is positive and n is divisible by n - b. For "abab", lps ends in 2, block length 2, and 4 is divisible by 2. Time O(n), space O(n).. Edge cases: single character (false), "aaaa" (true), "abaab" (border exists but length not divisible).
pythondef repeated_substring_pattern(s): n = len(s) if n < 2: return False b = build_lps(s)[-1] return b > 0 and n % (n - b) == 0javaimport java.util.*; class Solution { static boolean repeatedSubstringPattern(String s) { int n = s.length(); if (n < 2) return false; int b = buildLps(s)[n - 1]; return b > 0 && n % (n - b) == 0; } // buildLps is the method from the LPS problem }7 Repeated string match: the smallest number of times to repeat a so that b becomes a substring, or -1.
mediumIf b is a substring of some repetition of a, it fits inside ceil(len(b) / len(a)) copies or one more, because b can start in the middle of a copy and spill over. Try those two repeat counts with a substring search. If neither contains b, no number of repeats will. A KMP search keeps each check linear. Time O(len(a) * repeats + len(b)) with KMP, worst case worse with the naive built-in search; space O(len(a) * repeats).. Edge cases: b longer than a, b shorter than a, letters in b missing from a (-1).
pythondef repeated_string_match(a, b): times = -(-len(b) // len(a)) for t in (times, times + 1): if b in a * t: return t return -1javaimport java.util.*; class Solution { static int repeatedStringMatch(String a, String b) { int times = (b.length() + a.length() - 1) / a.length(); StringBuilder sb = new StringBuilder(a.repeat(times)); for (int t = times; t <= times + 1; t++) { if (sb.indexOf(b) >= 0) return t; sb.append(a); } return -1; } }8 Rabin-Karp: search for a pattern using a rolling hash.
mediumCompute a polynomial hash of the pattern and of the first window of the text. Slide the window one character at a time, updating the hash in O(1): remove the leading character times base^(m-1), multiply by the base, add the new character. When hashes match, compare the actual strings to rule out collisions. Expected time is linear with a good modulus. Time O(n + m) expected, O(n * m) worst case with many collisions; space O(1).. Edge cases: pattern longer than text, hash collisions (the verification step is essential), negative values after subtraction in Java.
pythondef rabin_karp(s, p): n, m = len(s), len(p) if m == 0: return 0 if m > n: return -1 B, MOD = 256, 1_000_000_007 high = pow(B, m - 1, MOD) hp = hs = 0 for i in range(m): hp = (hp * B + ord(p[i])) % MOD hs = (hs * B + ord(s[i])) % MOD for i in range(n - m + 1): if hp == hs and s[i:i + m] == p: return i if i < n - m: hs = ((hs - ord(s[i]) * high) * B + ord(s[i + m])) % MOD return -1javaimport java.util.*; class Solution { static int rabinKarp(String s, String p) { int n = s.length(), m = p.length(); if (m == 0) return 0; if (m > n) return -1; final long B = 256, MOD = 1_000_000_007L; long high = 1, hp = 0, hs = 0; for (int i = 0; i < m - 1; i++) high = high * B % MOD; for (int i = 0; i < m; i++) { hp = (hp * B + p.charAt(i)) % MOD; hs = (hs * B + s.charAt(i)) % MOD; } for (int i = 0; i + m <= n; i++) { if (hp == hs && s.startsWith(p, i)) return i; if (i + m < n) { hs = ((hs - s.charAt(i) * high % MOD + MOD) * B + s.charAt(i + m)) % MOD; } } return -1; } }9 Shortest palindrome: the shortest palindrome you can make by adding characters only in front of s.
hardYou need the longest prefix of s that is already a palindrome; the rest of s, reversed, goes in front. Build t = s + "#" + reverse(s) and compute its prefix function. The last value is the length of the longest palindromic prefix of s. The separator stops a border from crossing between the two halves. For "aacecaaa" the answer is "aaacecaaa". Time O(n), space O(n).. Edge cases: empty string, a string that is already a palindrome, no palindromic prefix longer than one character.
pythondef shortest_palindrome(s): if not s: return s t = s + "#" + s[::-1] k = build_lps(t)[-1] return s[k:][::-1] + sjavaimport java.util.*; class Solution { static String shortestPalindrome(String s) { if (s.isEmpty()) return s; String t = s + "#" + new StringBuilder(s).reverse(); int k = buildLps(t)[t.length() - 1]; return new StringBuilder(s.substring(k)).reverse() + s; } // buildLps is the method from the LPS problem }10 The Z-function: for each position, the length of the longest common prefix of the string and the suffix starting there.
hardMaintain a window [l, r) that is the rightmost segment known to match a prefix. For a new i inside the window, start with min(r - i, z[i - l]), since the window mirrors the prefix. Then extend by direct comparison and move the window if it grows. To search for p in s, compute the Z-array of p + "#" + s and report positions where z equals len(p). Time O(n), space O(n).. Edge cases: single character, all equal characters, a string with no repeated prefix.
pythondef z_function(s): n = len(s) z = [0] * n l = r = 0 for i in range(1, n): if i < r: z[i] = min(r - i, z[i - l]) while i + z[i] < n and s[z[i]] == s[i + z[i]]: z[i] += 1 if i + z[i] > r: l, r = i, i + z[i] return zjavaimport java.util.*; class Solution { static int[] zFunction(String s) { int n = s.length(); int[] z = new int[n]; int l = 0, r = 0; for (int i = 1; i < n; i++) { if (i < r) z[i] = Math.min(r - i, z[i - l]); while (i + z[i] < n && s.charAt(z[i]) == s.charAt(i + z[i])) z[i]++; if (i + z[i] > r) { l = i; r = i + z[i]; } } return z; } }
Frequently asked questions
Why is KMP linear?
The text pointer never moves backwards, and the matched length k increases by at most one per text character. Each fallback reduces k, so total fallbacks cannot exceed total increases, giving O(n + m).
What is the difference between KMP and Rabin-Karp?
KMP is deterministic and linear in the worst case, using a table built from the pattern. Rabin-Karp uses hashing, is linear on average and extends easily to many patterns, but needs collision checks.
Do I need to write KMP from memory in interviews?
Occasionally. Most interviews accept the built-in search for plain matching, but problems about prefixes, borders and repetition are built on the prefix function, so know how to write it.
What is a border of a string?
A non-empty proper prefix that is also a suffix. The prefix function stores the length of the longest border for each prefix of the string.
Where do I practise general substring problems?
See string questions for palindromes and parsing, and hashing questions for hash-based approaches.
Related guides
- String interview questions with worked solutions
- Sliding window interview questions with worked solutions
- Hashing interview questions with worked solutions
- Recursion interview questions with worked solutions
- Binary search interview questions with worked solutions
- Two pointers interview questions with worked solutions
More in DSA Interview Questions
- Knapsack DP Interview Questions
- Linked list interview questions with worked solutions
- Longest Common Subsequence (LCS) Interview Questions
- Longest Increasing Subsequence (LIS) Interview Questions
- LRU Cache and Design Data Structure Interview Questions
- Math and number theory interview questions with solutions
- Matrix interview questions with worked solutions
- Merge intervals pattern questions with worked solutions
- Minimum Spanning Tree Interview Questions
- Monotonic stack interview questions with worked solutions
- Prefix sum interview questions with worked solutions
- Queue and deque interview questions with worked solutions