String matching, hashing, and palindrome · HTML
pi[i] is the length of the longest proper prefix of pattern[0..i] that is also a suffix; j tracks the reusable prefix while scanning.
Recognition signals
- One-pattern exact matching
- A worst-case O(n+m) bound matters
- Overlapping matches are required
- Borders or periods are relevant
- Naive slicing may cost O(nm)
False friends
| Signal | Why it is different |
|---|
| Many patterns | Shared structure across patterns calls for a trie or multi-pattern automaton. |
| Approximate matching | Allowed edits or errors require DP or another distance method. |
Core invariant
Before processing the next text character, j is the maximum prefix length equal to a suffix of the processed text.
State, transition, and processing order
| Item | Definition |
|---|
| State | The pattern prefix-function pi, current matched length j, and match starts. |
| Transition | On mismatch follow pi[j-1]; on equality increment j; at j==m report and fall back to permit overlap. |
| Frontier / order | The text pointer moves only right; the pattern frontier retreats along border links without rereading text. |
Python skeleton
def kmp_find_all(text, pat):
if not pat: return list(range(len(text)+1))
pi = [0] * len(pat)
j = 0
for i in range(1, len(pat)):
while j and pat[i] != pat[j]: j = pi[j-1]
if pat[i] == pat[j]: j += 1
pi[i] = j
ans, j = [], 0
for i, ch in enumerate(text):
while j and ch != pat[j]: j = pi[j-1]
if ch == pat[j]: j += 1
if j == len(pat):
ans.append(i-len(pat)+1)
j = pi[j-1]
return ans
Correctness sketch
- pi records the longest reusable border of each pattern prefix.
- After mismatch, every longer candidate is disproved, so pi[j-1] skips no match.
- j==m exactly when the full pattern is a suffix ending at the current text position.
- The text never retreats and total movement of j is linear.
Complexity
| Time | Space | Parameters |
|---|
| O(n+m) | O(m) plus output | text length n and pattern length m |
Edge cases
- Define empty-pattern semantics
- Pattern longer than text
- Highly repetitive characters
- Fall back after a match to find overlaps
- Unicode normalization may change equality
Error patterns
| Pattern | Why it fails / fix |
|---|
| Resetting to zero on mismatch | This discards a reusable border. |
| Falling back only once | The next candidate may still mismatch, so use while. |
| No fallback after a full match | This can index past the pattern and misses overlaps. |
Selection and exclusion rules
- One exact pattern with a worst-case guarantee: KMP.
- Many equal-length substring comparisons: rolling hash.
- Many patterns: trie or multi-pattern automaton.
- For one short engineering lookup, a built-in find may be clearest.
Original micro-example
| Part | Detail |
|---|
| Result | Matches start at 0 and 2. |
| Scenario | Text ababab and pattern abab. |
| Walkthrough | After the first match, j falls to the border ab of length 2; two more characters complete the overlapping match. |
Recall prompts
My notes