String Algorithms
The pattern: Naive substring search is O(n·m) because every mismatch throws away everything you just matched and restarts the text pointer one character later. KMP, Rabin-Karp and the Z-function all buy you the same thing: you never re-compare a prefix you have already matched.
Why this matters in interviews: String problems are the largest category on most interview lists, and a handful of them collapse the moment you know the failure function. “Shortest palindrome,” “repeated substring pattern,” “count all occurrences with overlap” — these are two-line problems once you have the LPS array and unsolvable-looking without it.
When to Recognize It
- You need all occurrences of a pattern, not just the first, and they can overlap
- The question is about periodicity: does this string repeat? what is its smallest period?
nis up to 10⁵ or 10⁶ and the text is adversarial (long runs of one character)- You need to search many patterns in one text, or match a 2D block inside a grid
- Keywords: “shortest palindrome,” “prefix that is also a suffix,” “smallest repeating unit”
- The problem compares substrings repeatedly and you want each comparison to be O(1)
How It Works
Start with the obvious algorithm. Line the pattern up at position 0, compare left to right, and on the first mismatch slide the pattern one step right and start over.
That is fine until the text and the pattern share a lot of structure. Search "aaab" inside "aaaaaaaab":
text: a a a a a a a b (9 chars, index 0-8)
pattern: a a a b (4 chars)
start=0: 3 'a's match, then 'b' vs 'a' -> fail (4 comparisons)
start=1: same story -> fail (4 comparisons)
start=2, 3, 4: same story -> fail (4 each)
start=5: a a a b -> MATCH
24 character comparisons to scan 9 characters.
Scale that up. A text of 10⁵ as against the pattern "aaa...ab" of length 10³ costs about 10⁸ comparisons, and that is exactly the input an interviewer uses to break a naive solution.
Here is the waste: at start=0 you learned that text[0..2] is "aaa". At start=1 you read text[1] and text[2] again even though you already know what they hold. The pattern’s own structure told you in advance that after matching "aaa" and failing, the next viable alignment keeps two of those as.
flowchart LR
T["text pointer<br/>only moves forward"]:::client
M["mismatch at<br/>pattern index j"]:::service
L["lps table<br/>precomputed"]:::data
R["resume at<br/>pattern index lps j-1"]:::service
T --> M
M -->|"ask the table how much to keep"| L
L --> R
R --> T
classDef client fill:#4c3a5e,stroke:#818cf8,color:#e2e8f0
classDef service fill:#1a3a2a,stroke:#4ade80,color:#e2e8f0
classDef data fill:#3b3520,stroke:#fbbf24,color:#e2e8f0
That table lookup is all three algorithms in one sentence. They differ in what the table holds.
1. KMP - Never Re-Compare a Matched Prefix
The failure function, usually called the LPS array, is the whole algorithm. The search loop around it is six lines.
What lps[i] means: the length of the longest proper prefix of pattern[0..i] that is also a suffix of pattern[0..i]. Proper means it cannot be the whole thing, otherwise the answer would always be i + 1 and tell you nothing.
Build it by hand for "ababaca". For each prefix, find the longest border - a string that shows up both at the front and at the back.
i prefix longest border lps[i]
0 a none 0
1 ab none 0
2 aba "a" 1
3 abab "ab" 2
4 ababa "aba" 3
5 ababac none 0
6 ababaca "a" 1
lps = [0, 0, 1, 2, 3, 0, 1]
Now the mechanical build, which is what you actually write. Carry a variable length holding the border length from the previous position and extend it when the next character cooperates:
i=1 length=0 p[1]='b' vs p[0]='a' mismatch, length is 0 -> lps[1]=0
i=2 length=0 p[2]='a' vs p[0]='a' match -> length=1 -> lps[2]=1
i=3 length=1 p[3]='b' vs p[1]='b' match -> length=2 -> lps[3]=2
i=4 length=2 p[4]='a' vs p[2]='a' match -> length=3 -> lps[4]=3
i=5 length=3 p[5]='c' vs p[3]='b' mismatch, fall back: length=lps[2]=1
i=5 length=1 p[5]='c' vs p[1]='b' mismatch, fall back: length=lps[0]=0
i=5 length=0 p[5]='c' vs p[0]='a' mismatch, length is 0 -> lps[5]=0
i=6 length=0 p[6]='a' vs p[0]='a' match -> length=1 -> lps[6]=1
The fall-back line is the one people get wrong. When the border of length length fails to extend, the next candidate is not length - 1, it is lps[length - 1] - the longest border of that border. A border of a border is still a border of the original, so that chain visits exactly the viable candidates and skips everything else.
Why this kills backtracking in the text. Search "ababaca" inside "abababaca":
text : a b a b a b a c a
pattern : a b a b a c a
text[0..4]="ababa" matches pattern[0..4]. Then text[5]='b' vs pattern[5]='c' -> mismatch.
Naive restarts at text index 1 and re-reads text[1], text[2], ...
KMP keeps lps[4] = 3 of the 5 matched characters, the "aba" suffix.
Resume at pattern[3]='b' against the SAME text[5]='b'. Match.
pattern[4]='a' vs text[6]='a'; pattern[5]='c' vs text[7]='c'; pattern[6]='a' vs text[8]='a'.
All 7 matched -> occurrence starts at 8 - 7 + 1 = 2.
The text pointer went 0, 1, 2 ... 8 and never once went backward.
That is the guarantee. i only increases, so the search is O(n) no matter how pathological the input. The inner while looks like it could be quadratic, but matched only shrinks there and it only ever grew n times in total.
Counting all occurrences: after a full match, set
matched = lps[m - 1]rather than0. Resetting to zero loses overlapping hits - searching"aaa"in"aaaaa"should return three matches, not one.
Code
def build_lps(pattern):
"""lps[i] = longest proper prefix of pattern[:i+1] that is also its suffix."""
lps = [0] * len(pattern)
length = 0 # border length carried from the previous index
for i in range(1, len(pattern)):
while length > 0 and pattern[i] != pattern[length]:
length = lps[length - 1] # border of the border, not length - 1
if pattern[i] == pattern[length]:
length += 1
lps[i] = length
return lps
def kmp_search(text, pattern):
"""Every start index where pattern occurs in text, overlaps included."""
if not pattern:
return []
lps = build_lps(pattern)
matches, matched = [], 0 # matched = how many pattern chars are aligned
for i, ch in enumerate(text):
while matched > 0 and ch != pattern[matched]:
matched = lps[matched - 1]
if ch == pattern[matched]:
matched += 1
if matched == len(pattern):
matches.append(i - matched + 1)
matched = lps[matched - 1] # keep overlaps alive
return matchesint[] buildLps(String pattern) {
int[] lps = new int[pattern.length()];
int length = 0; // border length carried from the previous index
for (int i = 1; i < pattern.length(); i++) {
while (length > 0 && pattern.charAt(i) != pattern.charAt(length))
length = lps[length - 1]; // border of the border
if (pattern.charAt(i) == pattern.charAt(length)) length++;
lps[i] = length;
}
return lps;
}
List<Integer> kmpSearch(String text, String pattern) {
List<Integer> matches = new ArrayList<>();
if (pattern.isEmpty()) return matches;
int[] lps = buildLps(pattern);
int matched = 0;
for (int i = 0; i < text.length(); i++) {
char c = text.charAt(i);
while (matched > 0 && c != pattern.charAt(matched))
matched = lps[matched - 1];
if (c == pattern.charAt(matched)) matched++;
if (matched == pattern.length()) {
matches.add(i - matched + 1);
matched = lps[matched - 1]; // keep overlaps alive
}
}
return matches;
}vector<int> buildLps(const string& pattern) {
vector<int> lps(pattern.size(), 0);
int length = 0; // border length carried from the previous index
for (int i = 1; i < (int)pattern.size(); i++) {
while (length > 0 && pattern[i] != pattern[length])
length = lps[length - 1]; // border of the border
if (pattern[i] == pattern[length]) length++;
lps[i] = length;
}
return lps;
}
vector<int> kmpSearch(const string& text, const string& pattern) {
vector<int> matches;
if (pattern.empty()) return matches;
vector<int> lps = buildLps(pattern);
int matched = 0, m = pattern.size();
for (int i = 0; i < (int)text.size(); i++) {
while (matched > 0 && text[i] != pattern[matched])
matched = lps[matched - 1];
if (text[i] == pattern[matched]) matched++;
if (matched == m) {
matches.push_back(i - matched + 1);
matched = lps[matched - 1]; // keep overlaps alive
}
}
return matches;
}function buildLps(pattern) {
const lps = new Array(pattern.length).fill(0);
let length = 0; // border length carried from the previous index
for (let i = 1; i < pattern.length; i++) {
while (length > 0 && pattern[i] !== pattern[length])
length = lps[length - 1]; // border of the border
if (pattern[i] === pattern[length]) length++;
lps[i] = length;
}
return lps;
}
function kmpSearch(text, pattern) {
if (pattern.length === 0) return [];
const lps = buildLps(pattern);
const matches = [];
let matched = 0;
for (let i = 0; i < text.length; i++) {
while (matched > 0 && text[i] !== pattern[matched])
matched = lps[matched - 1];
if (text[i] === pattern[matched]) matched++;
if (matched === pattern.length) {
matches.push(i - matched + 1);
matched = lps[matched - 1]; // keep overlaps alive
}
}
return matches;
}The periodicity bonus: for a string of length m, if m % (m - lps[m - 1]) == 0 then the string is a whole number of repeats of a block of size m - lps[m - 1]. That single line solves Repeated Substring Pattern.
2. Rabin-Karp - Hash the Window Instead
KMP compares characters cleverly. Rabin-Karp stops comparing characters at all. It reads each window of the text as a number and compares numbers.
hash("abc") with BASE = 256:
'a'*256^2 + 'b'*256^1 + 'c'*256^0 (all mod M)
Rolling from window [i, i+m-1] to [i+1, i+m]:
1. drop the leading char: h -= text[i] * BASE^(m-1)
2. shift everything left: h *= BASE
3. admit the new char: h += text[i+m]
take mod M after every step
BASE^(m-1) is precomputed once, so each slide costs one subtract, one multiply, one add. O(1) per position, O(n) for the scan.
Why a large prime modulus. Without a modulus, the hash of a 20-character window overflows any integer type and the arithmetic turns to garbage. A modulus keeps the values bounded, and a prime one spreads them evenly - a power-of-two modulus just throws away the high bits, and a composite one clusters windows that share a factor with it. 1_000_000_007 and 1_000_000_009 are the standard picks because BASE × M still fits comfortably in 64 bits.
Equal hashes are a candidate, not a match. Two different windows can hash the same. At M ≈ 10⁹ that is rare but not impossible, and competitive test sets are sometimes built specifically to break a fixed base. So every hash hit gets confirmed with a direct character comparison. Verification is O(m) but only runs on hits, which keeps the expected total at O(n + m). Force a collision at every position and you are back to O(n·m) - which is why KMP, not Rabin-Karp, is the one with a worst-case guarantee.
Hardening it: pick the base randomly at run time, or carry two hashes with different moduli and require both to agree.
When the rolling hash is the better tool: one text and 50 patterns of the same length - hash all 50 into a set and the scan is still one pass. Or a grid where you need a k × k block: hash each row-window, then roll vertically over the row hashes. KMP generalises to neither of those cleanly.
Code
BASE = 256 # alphabet size, any value > max char code works
MOD = 1_000_000_007 # large prime keeps collisions rare and values bounded
def rabin_karp(text, pattern):
n, m = len(text), len(pattern)
if m == 0 or m > n:
return []
high_pow = pow(BASE, m - 1, MOD) # place value of the leading character
pattern_hash = window_hash = 0
for i in range(m):
pattern_hash = (pattern_hash * BASE + ord(pattern[i])) % MOD
window_hash = (window_hash * BASE + ord(text[i])) % MOD
matches = []
for start in range(n - m + 1):
# hash equality is only a candidate - confirm the characters
if window_hash == pattern_hash and text[start:start + m] == pattern:
matches.append(start)
if start + m < n:
window_hash = (window_hash - ord(text[start]) * high_pow) % MOD
window_hash = (window_hash * BASE + ord(text[start + m])) % MOD
return matchesstatic final long BASE = 256, MOD = 1_000_000_007L;
List<Integer> rabinKarp(String text, String pattern) {
int n = text.length(), m = pattern.length();
List<Integer> matches = new ArrayList<>();
if (m == 0 || m > n) return matches;
long highPow = 1; // BASE^(m-1) mod MOD
for (int i = 0; i < m - 1; i++) highPow = highPow * BASE % MOD;
long patternHash = 0, windowHash = 0;
for (int i = 0; i < m; i++) {
patternHash = (patternHash * BASE + pattern.charAt(i)) % MOD;
windowHash = (windowHash * BASE + text.charAt(i)) % MOD;
}
for (int start = 0; start + m <= n; start++) {
if (windowHash == patternHash
&& text.regionMatches(start, pattern, 0, m)) { // verify
matches.add(start);
}
if (start + m < n) {
// + MOD before the final % keeps the result non-negative
windowHash = (windowHash - text.charAt(start) * highPow % MOD + MOD) % MOD;
windowHash = (windowHash * BASE + text.charAt(start + m)) % MOD;
}
}
return matches;
}const long long BASE = 256, MOD = 1000000007LL;
vector<int> rabinKarp(const string& text, const string& pattern) {
int n = text.size(), m = pattern.size();
vector<int> matches;
if (m == 0 || m > n) return matches;
long long highPow = 1; // BASE^(m-1) mod MOD
for (int i = 0; i < m - 1; i++) highPow = highPow * BASE % MOD;
long long patternHash = 0, windowHash = 0;
for (int i = 0; i < m; i++) {
patternHash = (patternHash * BASE + pattern[i]) % MOD;
windowHash = (windowHash * BASE + text[i]) % MOD;
}
for (int start = 0; start + m <= n; start++) {
// compare(pos, len, str) returns 0 on an exact match
if (windowHash == patternHash && text.compare(start, m, pattern) == 0)
matches.push_back(start);
if (start + m < n) {
windowHash = (windowHash - text[start] * highPow % MOD + MOD) % MOD;
windowHash = (windowHash * BASE + text[start + m]) % MOD;
}
}
return matches;
}const BASE = 256, MOD = 1000000007;
function rabinKarp(text, pattern) {
const n = text.length, m = pattern.length;
if (m === 0 || m > n) return [];
let highPow = 1; // BASE^(m-1) mod MOD
for (let i = 0; i < m - 1; i++) highPow = (highPow * BASE) % MOD;
let patternHash = 0, windowHash = 0;
for (let i = 0; i < m; i++) {
patternHash = (patternHash * BASE + pattern.charCodeAt(i)) % MOD;
windowHash = (windowHash * BASE + text.charCodeAt(i)) % MOD;
}
const matches = [];
for (let start = 0; start + m <= n; start++) {
if (windowHash === patternHash && text.substr(start, m) === pattern)
matches.push(start);
if (start + m < n) {
// every product stays under 2^53 because we mod after each step
const drop = (text.charCodeAt(start) * highPow) % MOD;
windowHash = (windowHash - drop + MOD) % MOD;
windowHash = (windowHash * BASE + text.charCodeAt(start + m)) % MOD;
}
}
return matches;
}3. Z-Function - Prefix Match Lengths
z[i] is the length of the longest substring starting at position i that is also a prefix of the whole string. z[0] is set to n or left undefined by convention; nobody reads it.
Work it out on "aabaab":
s = a a b a a b
0 1 2 3 4 5
z[1]: s[1]='a' matches s[0]='a'; s[2]='b' vs s[1]='a' stops -> 1
z[2]: s[2]='b' vs s[0]='a' stops immediately -> 0
z[3]: s[3..5]="aab" vs prefix "aab", all three match, end hit -> 3
z[4]: s[4]='a' matches s[0]; s[5]='b' vs s[1]='a' stops -> 1
z[5]: s[5]='b' vs s[0]='a' stops -> 0
z = [-, 1, 0, 3, 1, 0]
The O(n) trick is a window [left, right) marking the rightmost prefix-match found so far. When i falls inside that window you already know the characters there - they are a copy of s[i - left ...] - so z[i] starts at min(right - i, z[i - left]) instead of zero. Only the stretch past right is ever compared character by character, and right only moves forward.
How it relates to KMP. Both arrays encode “how much of the prefix shows up here,” anchored differently. lps[i] looks backward and asks for the longest border of the prefix ending at i. z[i] looks forward and asks how far the prefix is reproduced from i. They convert to each other in O(n). Z usually reads easier for counting and periodicity; KMP wins when the text is a stream you cannot concatenate.
Matching with Z. Build pattern + separator + text, run the Z-function over it, and every index where z[i] == len(pattern) is an occurrence at text position i - len(pattern) - 1. The separator must be a character that appears in neither string, or a match can run across the boundary and overcount.
Code
def z_function(s):
"""z[i] = length of the longest prefix of s that starts at index i."""
n = len(s)
z = [0] * n
z[0] = n
left = right = 0 # [left, right) = rightmost prefix match seen
for i in range(1, n):
if i < right:
z[i] = min(right - i, z[i - left]) # reuse the mirrored answer
while i + z[i] < n and s[z[i]] == s[i + z[i]]:
z[i] += 1 # only ever extends past 'right'
if i + z[i] > right:
left, right = i, i + z[i]
return z
def z_search(text, pattern):
sep = "\x00" # must not occur in either string
combined = pattern + sep + text
z = z_function(combined)
m = len(pattern)
return [i - m - 1 for i in range(m + 1, len(combined)) if z[i] == m]int[] zFunction(String s) {
int n = s.length();
int[] z = new int[n];
z[0] = n;
int left = 0, right = 0; // [left, right) = rightmost prefix match seen
for (int i = 1; i < n; i++) {
if (i < right) z[i] = Math.min(right - i, z[i - left]);
while (i + z[i] < n && s.charAt(z[i]) == s.charAt(i + z[i])) z[i]++;
if (i + z[i] > right) { left = i; right = i + z[i]; }
}
return z;
}
List<Integer> zSearch(String text, String pattern) {
int m = pattern.length();
String combined = pattern + '\u0000' + text; // separator in neither string
int[] z = zFunction(combined);
List<Integer> matches = new ArrayList<>();
for (int i = m + 1; i < combined.length(); i++)
if (z[i] == m) matches.add(i - m - 1);
return matches;
}vector<int> zFunction(const string& s) {
int n = s.size();
vector<int> z(n, 0);
z[0] = n;
int left = 0, right = 0; // [left, right) = rightmost prefix match seen
for (int i = 1; i < n; i++) {
if (i < right) z[i] = min(right - i, z[i - left]);
while (i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++;
if (i + z[i] > right) { left = i; right = i + z[i]; }
}
return z;
}
vector<int> zSearch(const string& text, const string& pattern) {
int m = pattern.size();
string combined = pattern + '\0' + text; // separator in neither string
vector<int> z = zFunction(combined), matches;
for (int i = m + 1; i < (int)combined.size(); i++)
if (z[i] == m) matches.push_back(i - m - 1);
return matches;
}function zFunction(s) {
const n = s.length;
const z = new Array(n).fill(0);
z[0] = n;
let left = 0, right = 0; // [left, right) = rightmost prefix match seen
for (let i = 1; i < n; i++) {
if (i < right) z[i] = Math.min(right - i, z[i - left]);
while (i + z[i] < n && s[z[i]] === s[i + z[i]]) z[i]++;
if (i + z[i] > right) { left = i; right = i + z[i]; }
}
return z;
}
function zSearch(text, pattern) {
const m = pattern.length;
const combined = pattern + "\u0000" + text; // separator in neither string
const z = zFunction(combined);
const matches = [];
for (let i = m + 1; i < combined.length; i++)
if (z[i] === m) matches.push(i - m - 1);
return matches;
}4. Palindromes - Expand Around Centre
A palindrome is defined by its centre, and a string of length n has 2n - 1 candidate centres: n single characters and n - 1 gaps between characters. Walk outward from each while the two sides agree. O(n²) time, O(1) space, about eight lines.
s = "babad"
centre 'b'@0 -> "b", length 1
gap between 0 and 1 -> b vs a, length 0
centre 'a'@1 -> s[0]='b' == s[2]='b' -> "bab", then index -1, length 3
gap between 1 and 2 -> a vs b, length 0
centre 'b'@2 -> s[1]='a' == s[3]='a' -> "aba", then 'd' != 'b', length 3
best = "bab", tied with "aba", either is accepted
This is the answer to give in an interview. Easy to write without bugs, easy to explain, and the two-centres-per-index detail is the only place to slip.
Manacher’s algorithm does the same job in O(n) with the same mirror trick as the Z-function - keep the rightmost palindrome found and reuse radii from inside it. Plainly: you will almost never be asked to produce Manacher at a whiteboard, and reaching for it unprompted costs more time than the O(n²) version loses. Know it exists, know O(n) is achievable, and write it only if the constraints are at 10⁶ and the interviewer pushes.
Code
def longest_palindrome(s):
if not s:
return ""
best_start, best_len = 0, 1
def expand(left, right):
"""Widen while the ends match; return (start, length) of the result."""
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
return left + 1, right - left - 1 # ends overshot by one on each side
for centre in range(len(s)):
for lo, hi in ((centre, centre), (centre, centre + 1)): # odd then even
start, length = expand(lo, hi)
if length > best_len:
best_start, best_len = start, length
return s[best_start:best_start + best_len]String longestPalindrome(String s) {
if (s.isEmpty()) return "";
int bestStart = 0, bestLen = 1;
for (int centre = 0; centre < s.length(); centre++) {
int[][] pairs = {{centre, centre}, {centre, centre + 1}}; // odd, even
for (int[] p : pairs) {
int left = p[0], right = p[1];
while (left >= 0 && right < s.length()
&& s.charAt(left) == s.charAt(right)) { left--; right++; }
int length = right - left - 1; // both ends overshot by one
if (length > bestLen) { bestLen = length; bestStart = left + 1; }
}
}
return s.substring(bestStart, bestStart + bestLen);
}string longestPalindrome(const string& s) {
if (s.empty()) return "";
int bestStart = 0, bestLen = 1, n = s.size();
for (int centre = 0; centre < n; centre++) {
for (int even = 0; even < 2; even++) { // 0 = odd, 1 = even centre
int left = centre, right = centre + even;
while (left >= 0 && right < n && s[left] == s[right]) { left--; right++; }
int length = right - left - 1; // ends overshot by one
if (length > bestLen) { bestLen = length; bestStart = left + 1; }
}
}
return s.substr(bestStart, bestLen);
}function longestPalindrome(s) {
if (s.length === 0) return "";
let bestStart = 0, bestLen = 1;
for (let centre = 0; centre < s.length; centre++) {
for (const offset of [0, 1]) { // odd centre, then even
let left = centre, right = centre + offset;
while (left >= 0 && right < s.length && s[left] === s[right]) {
left--; right++;
}
const length = right - left - 1; // ends overshot by one
if (length > bestLen) { bestLen = length; bestStart = left + 1; }
}
}
return s.slice(bestStart, bestStart + bestLen);
}When the Built-In Is the Right Answer
Writing KMP for a problem that did not need it is a mistake of its own: 25 lines where one would do, and every one of them a place to put an off-by-one under time pressure. Use str.find / indexOf / std::string::find when:
n × mcomfortably fits the budget. At a rough 10⁸ simple operations per second,n = 10⁴withm = 100is 10⁶ and nowhere near trouble.- You need the first occurrence only, on ordinary text rather than a long run of one character.
- The search is a detail inside a bigger problem. If the real work is dynamic programming, do not spend your thinking budget on the scan.
The built-ins are also better than you think. CPython’s str.find is not a naive double loop - stringlib runs a Boyer-Moore-Horspool variant with a Bloom-filter skip table, and a two-way algorithm for long needles, so it handles the repetitive worst case well. Java’s String.indexOf genuinely is the naive scan, but JIT-compiled with a tiny constant factor, which is why it still beats hand-written KMP on short inputs.
Write the real algorithm when you need all overlapping occurrences, when the question is about periods and borders, when n reaches 10⁶, or when the interviewer says “implement it yourself.”
Complexity
| Algorithm | Build | Search | Extra space |
|---|---|---|---|
| Naive | none | O(n·m) worst | O(1) |
| KMP | O(m) | O(n) guaranteed | O(m) |
| Rabin-Karp | O(m) | O(n + m) expected | O(1) |
| Z-function | O(n + m) | included in build | O(n + m) |
KMP is the only one with a worst case you can promise an interviewer. Rabin-Karp degrades to O(n·m) if every window collides, which requires either terrible luck or a deliberately constructed test. The Z-function’s space cost comes from materialising the array over pattern + separator + text, so it is the wrong choice if the text is a stream you cannot hold in memory.
Common Mistakes
- Off-by-one in the LPS array. The fall-back is
length = lps[length - 1], notlps[length]and notlength - 1. Usinglps[length]reads the entry you are mid-way through computing; usinglength - 1skips viable borders and silently returns wrong match positions. - Forgetting to verify a rolling-hash candidate. Equal hashes mean “probably,” never “yes.” The verification is two lines and it is the difference between a correct solution and one that fails a hand-crafted test.
- Integer overflow in the hash.
'a' * 256^19overflows a 32-bitintlong before you notice. Uselongin Java,long longin C++, and take the modulus after every multiply, not once at the end. - Reaching for KMP when
n × malready fits. If the constraints sayn ≤ 10³, the naive loop is the correct engineering answer and you should say so out loud rather than writing a failure function. - Resetting
matched = 0after a full match. That skips overlapping occurrences. Set it tolps[m - 1]. - A separator that appears in the input.
pattern + "#" + textbreaks the moment the text legitimately contains#. Pick a character outside the stated alphabet, or use\x00.
Practice Problems
- Find the Index of the First Occurrence in a String — the canonical place to write KMP
- Repeated Substring Pattern — one line once you have the LPS array
- Shortest Palindrome — KMP on
s + separator + reverse(s) - Longest Duplicate Substring — binary search the length, rolling hash each candidate
- Distinct Echo Substrings — rolling hash for O(1) substring comparison
- Palindromic Substrings — expand around centre, count instead of maximising
- Valid Palindrome II — two pointers with a single allowed deletion
- Longest Palindromic Substring — the expand-around-centre template verbatim (practice on LeetCode directly)
Key Takeaways
- The LPS array answers one question: after matching
kcharacters and failing, how many can I keep? Everything else in KMP is bookkeeping around that answer. - KMP’s text pointer never moves backward, which is where the O(n) guarantee comes from - not from the pattern pointer.
- Rolling hashes turn substring equality into integer equality, which is what makes multi-pattern and 2D matching tractable. Always verify the hit.
z[i]andlps[i]carry the same information from opposite directions; learn whichever one you find easier to re-derive under pressure.- Expand-around-centre is the palindrome answer to give. Manacher exists, is O(n), and is almost never required.
- Knowing when not to write these matters as much as knowing how. A built-in
findon a 10³ input is the right call.
SensAI