string-algorithms

What this skill does

# String Algorithm Patterns

This reference covers seven foundational string algorithms used in competitive programming and technical interviews. Each pattern includes recognition signals, a core idea explanation, a Python template, and notes on edge cases and common mistakes. Use the pattern recognition table to match problem constraints to the right technique, then drill into the individual pattern section.

---

## Pattern Recognition Table

| Trigger Signals | Technique | Typical Complexity |
|---|---|---|
| Find pattern in text, exact match, prefix function | KMP | O(N + M) |
| Longest common prefix at each position, string period | Z-function | O(N) |
| Multiple pattern search, rolling hash, substring fingerprint | Rabin-Karp | O(N + M) average |
| Longest palindromic substring, count palindromes | Manacher's | O(N) |
| Fast substring comparison, equality checks in O(1) | String Hashing | O(N) preprocess, O(1) query |
| Lexicographic ordering of suffixes, LCP queries, substring counting | Suffix Array | O(N log N) build |
| Dictionary of patterns matched against text, multi-pattern search | Aho-Corasick | O(N + M + Z) |

Where N = text length, M = pattern length (or total pattern lengths), Z = number of matches.

---

## Constraint-to-Technique Mapping

- **Single pattern, exact match, N up to 10^6**: KMP or Z-function
- **All prefix-suffix overlaps**: KMP failure function gives overlap chain
- **String periodicity or repetition**: Z-function (period = smallest i where z[i] + i == N)
- **Multiple patterns, moderate count (< 100)**: Rabin-Karp with rolling hash
- **Multiple patterns, large dictionary (10^3+)**: Aho-Corasick automaton
- **Palindrome queries**: Manacher's for longest; hashing + binary search for arbitrary checks
- **Substring equality or comparison in O(1)**: Polynomial string hashing with double hash
- **Lexicographic queries, distinct substrings, LCP**: Suffix array + LCP array

---

### KMP (Knuth-Morris-Pratt)

**Recognition Signals**
- Find all occurrences of a pattern in a text
- Compute the longest proper prefix that is also a suffix (failure/border array)
- Pattern matching without backtracking on the text pointer

**Core Idea**

KMP preprocesses the pattern into a failure (prefix) function that records, for each position, the length of the longest proper prefix that is also a suffix. On mismatch, the failure function tells us where to resume comparison without re-scanning text characters, guaranteeing linear time.

**Python Template**

```python
def kmp_search(text: str, pattern: str) -> list[int]:
    """Return all starting indices where pattern occurs in text."""
    n, m = len(text), len(pattern)
    if m == 0:
        return []
    # Build failure function
    fail = [0] * m
    k = 0
    for i in range(1, m):
        while k > 0 and pattern[k] != pattern[i]:
            k = fail[k - 1]
        if pattern[k] == pattern[i]:
            k += 1
        fail[i] = k
    # Search
    matches: list[int] = []
    k = 0
    for i in range(n):
        while k > 0 and pattern[k] != text[i]:
            k = fail[k - 1]
        if pattern[k] == text[i]:
            k += 1
        if k == m:
            matches.append(i - m + 1)
            k = fail[k - 1]
    return matches
```

**Key Edge Cases**
- Empty pattern or empty text (return empty list)
- Pattern longer than text
- Overlapping matches (e.g., pattern "aa" in text "aaaa" yields [0, 1, 2])
- Pattern equals text exactly (single match at index 0)

**Common Mistakes**
- Off-by-one in failure function construction (loop must start at index 1, not 0)
- Forgetting to reset `k = fail[k - 1]` after a full match to allow overlapping matches
- Confusing 0-indexed vs 1-indexed failure arrays across reference implementations

---

### Z-function

**Recognition Signals**
- Compute the longest substring starting at each position that matches a prefix
- Detect string periods or smallest repeating units
- Alternative to KMP for single-pattern matching

**Core Idea**

The Z-array for a string S stores at each index i > 0 the length of the longest substring starting at i that matches a prefix of S. Construction runs in O(N) using a sliding window [l, r] tracking the rightmost Z-box. For pattern matching, concatenate pattern + separator + text and look for Z-values equal to the pattern length. Periodicity detection: the smallest period p satisfies z[p] + p == N.

**Python Template**

```python
def z_function(s: str) -> list[int]:
    """Compute the Z-array for string s."""
    n = len(s)
    z = [0] * n
    z[0] = n
    l, r = 0, 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 z


def z_search(text: str, pattern: str) -> list[int]:
    """Find all occurrences of pattern in text using Z-function."""
    combined = pattern + "$" + text
    z = z_function(combined)
    m = len(pattern)
    return [i - m - 1 for i in range(m + 1, len(combined)) if z[i] == m]
```

**Key Edge Cases**
- Single-character strings (Z[0] = N by definition, rest are trivial)
- Strings of all identical characters (every Z[i] = N - i)
- Separator character must not appear in pattern or text

**Common Mistakes**
- Forgetting to set z[0] = n (by convention, z[0] equals the full string length)
- Using a separator character that exists in the input alphabet
- Incorrect window update: the condition is `i + z[i] > r`, not `>=`

---

### Rabin-Karp

**Recognition Signals**
- Multiple pattern search in a single text
- Substring fingerprinting or equality via hashing
- Problems where average-case O(N + M) suffices and worst-case O(NM) is acceptable

**Core Idea**

Rabin-Karp computes a polynomial rolling hash for each text window matching the pattern length. The hash slides in O(1) by subtracting the outgoing character's contribution and adding the incoming one. Hash matches are confirmed by character comparison. For multi-pattern search, store all pattern hashes in a set.

**Python Template**

```python
def rabin_karp(text: str, pattern: str, base: int = 131, mod: int = 10**18 + 9) -> list[int]:
    """Return all starting indices where pattern occurs in text."""
    n, m = len(text), len(pattern)
    if m > n:
        return []
    # Precompute highest power
    power = pow(base, m - 1, mod)
    # Hash the pattern and first window
    p_hash = 0
    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
    matches: list[int] = []
    for i in range(n - m + 1):
        if t_hash == p_hash and text[i:i + m] == pattern:
            matches.append(i)
        if i + m < n:
            t_hash = (t_hash - ord(text[i]) * power) % mod
            t_hash = (t_hash * base + ord(text[i + m])) % mod
    return matches
```

**Key Edge Cases**
- Hash collisions requiring the string comparison fallback
- Very long patterns where power computation must use modular exponentiation
- Negative hash values in languages with signed modular arithmetic (Python handles correctly)

**Common Mistakes**
- Forgetting the confirmation step after a hash match (false positives)
- Using a small modulus that causes frequent collisions
- Off-by-one in the sliding window loop bounds

---

### Manacher's Algorithm

**Recognition Signals**
- Find the longest palindromic substring
- Count total palindromic substrings
- Compute palindrome radii at every center (both odd and even length)

**Core Idea**

Manacher's algorithm finds the maximum palindrome radius centered at each position in O(N). It processes odd-length and even-length palindromes separately. A center c and right boundary r track the rightmost palindrome; for each new position i, the mirror 2c - i provides an initial radius estimate that is then expanded, avoiding redundant comparisons.

**Python Template**

```python
def manacher(s: str