20. String Matching#
Theory#
Use string matching when you need to locate a pattern inside a text, exploit prefix/suffix overlap, detect periodicity, or scan for many patterns at once — usually beating the O(n·m) naive double loop.
| Algorithm | Time | Space | Best for |
|---|---|---|---|
| Brute force | O(n·m) | O(1) | Tiny inputs, one-off checks |
| KMP | O(n + m) | O(m) | Single-pattern search, overlap / LPS tricks |
| Rabin–Karp | O(n + m) avg* | O(1) | Rolling hash, multiple pattern checks |
| Z-algorithm | O(n + m) | O(m) | Prefix–suffix structure, period detection |
| Aho–Corasick | O(n + m + z) | O(m) | Many patterns in one pass (z = matches) |
* Rabin–Karp worst case is O(n·m) without strong hashing; use double hashing or mod arithmetic in contests.
1. KMP (Knuth–Morris–Pratt)#
Idea: preprocess the pattern into an LPS (longest proper prefix that is also suffix) array. When a mismatch happens, shift the pattern using LPS instead of restarting from the next text character.
def build_lps(pattern: str) -> list[int]:
lps = [0] * len(pattern)
length = 0
i = 1
while i < len(pattern):
if pattern[i] == pattern[length]:
length += 1
lps[i] = length
i += 1
elif length:
length = lps[length - 1]
else:
lps[i] = 0
i += 1
return lps
def kmp_search(text: str, pattern: str) -> int:
"""Return first index of pattern in text, or -1."""
if not pattern:
return 0
lps = build_lps(pattern)
i = j = 0
while i < len(text):
if text[i] == pattern[j]:
i += 1
j += 1
if j == len(pattern):
return i - j
elif j:
j = lps[j - 1]
else:
i += 1
return -1
When to use: LC 28 (strstr), LC 214 (shortest palindrome via s + "#" + rev(s)), any problem where a failed match still shares a proper prefix–suffix with the pattern.
2. Rabin–Karp (rolling hash)#
Idea: hash the pattern and each length-|pattern| window in the text. On hash collision, verify characters. Update the window hash in O(1) by subtracting the outgoing char and adding the incoming char.
def rabin_karp_search(text: str, pattern: str, base: int = 256, mod: int = 10**9 + 7) -> int:
n, m = len(text), len(pattern)
if m == 0:
return 0
if m > n:
return -1
def char_val(c: str) -> int:
return ord(c)
h = pow(base, m - 1, mod)
p_hash = t_hash = 0
for i in range(m):
p_hash = (p_hash * base + char_val(pattern[i])) % mod
t_hash = (t_hash * base + char_val(text[i])) % mod
for i in range(n - m + 1):
if p_hash == t_hash and text[i:i + m] == pattern:
return i
if i < n - m:
t_hash = (t_hash - char_val(text[i]) * h) % mod
t_hash = (t_hash * base + char_val(text[i + m])) % mod
t_hash = (t_hash + mod) % mod
return -1
When to use: LC 686 (is B inside repeated A?), multiple pattern probes, or when you want average O(1) window comparison instead of O(m) char-by-char checks.
3. Z-algorithm#
Idea: for string S, Z[i] = length of the longest substring starting at i that matches a prefix of S. Build Z in O(|S|) with a [L, R] "Z-box" window.
def build_z(s: str) -> list[int]:
n = len(s)
z = [0] * n
l = r = 0
for i in range(1, n):
if i <= r:
z[i] = min(r - i + 1, z[i - l])
while i + z[i] < n and s[z[i]] == s[i + z[i]]:
z[i] += 1
if i + z[i] - 1 > r:
l, r = i, i + z[i] - 1
return z
When to use: "longest prefix match starting at i" (alternative to KMP for strstr), finding string period (n - z[n-1] when n % period == 0), counting occurrences of a pattern embedded in pattern + separator + text.
4. Aho–Corasick (brief)#
Idea: insert all patterns into a trie, add failure links (like KMP LPS but for a trie), then scan the text once — each character follows trie edges or failure links.
When to use: many keywords in one text (virus signatures, word filters, LC-style multi-pattern search). Overkill for a single pattern; pair with a trie when patterns share prefixes (see 19. Tries).
Complexity: build O(total pattern length), scan O(n + z) where z is number of reported matches.
Problems at a glance#
| LC | Problem | |
|---|---|---|
| 28 | Find the Index of First Occurrence in a String | ↗ |
| 686 | Repeated String Match | ↗ |
| 214 | Shortest Palindrome | ↗ |
Problems#
Problem 1: Find the Index of First Occurrence in a String (Leetcode:28)#
Problem Statement
Given two strings haystack and needle, return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
Example 1:
Input: haystack = "sadbutsad", needle = "sad" Output: 0
Example 2:
Input: haystack = "leetcode", needle = "leeto" Output: -1
Constraints:
1 <= haystack.length, needle.length <= 10^4, lowercase English letters.
Code and Explanation
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
if not needle:
return 0
n, m = len(haystack), len(needle)
for i in range(n - m + 1):
if haystack[i:i + m] == needle:
return i
return -1
Slide a window of length m across haystack and compare substring to needle. Simple and fine for small inputs; each compare is O(m).
Time: O(n·m) · Space: O(1)
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
if not needle:
return 0
def build_lps(p: str) -> list[int]:
lps = [0] * len(p)
length = 0
i = 1
while i < len(p):
if p[i] == p[length]:
length += 1
lps[i] = length
i += 1
elif length:
length = lps[length - 1]
else:
lps[i] = 0
i += 1
return lps
lps = build_lps(needle)
i = j = 0
while i < len(haystack):
if haystack[i] == needle[j]:
i += 1
j += 1
if j == len(needle):
return i - j
elif j:
j = lps[j - 1]
else:
i += 1
return -1
- LPS tells how far we can shift
needleafter a mismatch while keeping a matching prefix. - Text pointer
inever moves backward → single pass overhaystack. - Canonical string-matching template; reuse
build_lpsin palindrome / periodicity problems.
Time: O(n + m) · Space: O(m)
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
if not needle:
return 0
combined = needle + "\x00" + haystack
z = [0] * len(combined)
l = r = 0
for i in range(1, len(combined)):
if i <= r:
z[i] = min(r - i + 1, z[i - l])
while i + z[i] < len(combined) and combined[z[i]] == combined[i + z[i]]:
z[i] += 1
if i + z[i] - 1 > r:
l, r = i, i + z[i] - 1
m = len(needle)
for i in range(m + 1, len(combined)):
if z[i] == m:
return i - m - 1
return -1
Build Z on needle + separator + haystack. Any position i in the haystack half with Z[i] == len(needle) is a match. Separator \x00 prevents false prefix overlap across the boundary.
Time: O(n + m) · Space: O(n + m)
Problem 2: Repeated String Match (Leetcode:686)#
Problem Statement
Given two strings a and b, return the minimum number of times you should repeat a so that b is a substring of the repeated string. If it is impossible, return -1.
Example 1:
Input: a = "abcd", b = "cdabcdab" Output: 3
Example 2:
Input: a = "a", b = "aa" Output: 2
Constraints:
1 <= a.length, b.length <= 10^4
Code and Explanation
class Solution:
def repeatedStringMatch(self, a: str, b: str) -> int:
n, m = len(a), len(b)
k = (m + n - 1) // n # ceil(m / n)
if b in a * k:
return k
if b in a * (k + 1):
return k + 1
return -1
Key insight: if b fits inside a repeated k times, it must fit in a * k or a * (k+1) where k = ceil(m/n). At most one extra copy beyond the minimum length is needed — misalignment can straddle only one boundary between copies.
Quick checks: b in a → 1; b in a + a → 2 (covers many small cases without building longer strings).
Time: O(n + m) · Space: O(n + m)
class Solution:
def repeatedStringMatch(self, a: str, b: str) -> int:
n, m = len(a), len(b)
k = (m + n - 1) // n
repeated = a * (k + 1)
idx = self._rk_search(repeated, b)
if idx == -1:
return -1
return (idx + m + n - 1) // n
def _rk_search(self, text: str, pattern: str) -> int:
mod, base = 10**9 + 7, 256
m = len(pattern)
h = pow(base, m - 1, mod)
p_hash = t_hash = 0
for i in range(m):
p_hash = (p_hash * base + ord(pattern[i])) % mod
t_hash = (t_hash * base + ord(text[i])) % mod
for i in range(len(text) - m + 1):
if p_hash == t_hash and text[i:i + m] == pattern:
return i
if i < len(text) - m:
t_hash = (t_hash - ord(text[i]) * h) % mod
t_hash = (t_hash * base + ord(text[i + m])) % mod
t_hash = (t_hash + mod) % mod
return -1
Build a * (k+1) (same periodicity bound), locate b with rolling hash, then convert start index to the minimum number of a copies: ceil((idx + m) / n).
Time: O(n + m) average · Space: O(n + m)
Problem 3: Shortest Palindrome (Leetcode:214)#
Problem Statement
You are given a string s. In one step you can insert any character at any position. Return the shortest palindrome you can get by performing this procedure.
Example 1:
Input: s = "aacecaaa" Output: "aaacecaaa"
Example 2:
Input: s = "abcd" Output: "dcbabcd"
Constraints:
0 <= s.length <= 5 * 10^4, lowercase English letters.
Code and Explanation
class Solution:
def shortestPalindrome(self, s: str) -> str:
if not s:
return s
def build_lps(p: str) -> list[int]:
lps = [0] * len(p)
length = 0
i = 1
while i < len(p):
if p[i] == p[length]:
length += 1
lps[i] = length
i += 1
elif length:
length = lps[length - 1]
else:
lps[i] = 0
i += 1
return lps
combined = s + "#" + s[::-1]
longest_pal_prefix = build_lps(combined)[-1]
return s[longest_pal_prefix:][::-1] + s
- Goal: find the longest palindromic prefix of
s. Prepend the reverse of the remaining suffix. - Build
combined = s + "#" + rev(s). The LPS value at the last index equals the longest border ofcombinedthat alignss's prefix withrev(s)'s suffix — i.e. longest palindromic prefix ofs. "#"(or any char not ins) preventssandrev(s)from falsely matching across the join.
Example: s = "aacecaaa" → longest palindromic prefix "aacecaa" (len 7) → prepend reverse of "a" → "aaacecaaa".
Time: O(n) · Space: O(n)
class Solution:
def shortestPalindrome(self, s: str) -> str:
n = len(s)
def is_pal_prefix(end: int) -> bool:
lo, hi = 0, end
while lo < hi:
if s[lo] != s[hi]:
return False
lo += 1
hi -= 1
return True
lo, hi = 0, n - 1
best = 0
while lo <= hi:
mid = (lo + hi) // 2
if is_pal_prefix(mid):
best = mid + 1
lo = mid + 1
else:
hi = mid - 1
return s[best:][::-1] + s
Binary search the longest palindromic prefix with O(n) verification each step → O(n log n). KMP is strictly better; included to show the same "find longest palindromic prefix" reduction without LPS.
Time: O(n log n) · Space: O(1)