AdvancedAdvanced Patterns

String Algorithms

Linear-time string matching and palindrome tricks: KMP, Z, rolling hash, Manacher

Time: O(n)
Space: O(n)
Pattern Overview

Core Idea

Precompute failure/overlap tables or rolling hashes to compare substrings in linear/sublinear time.

When to Use

Use for substring search, pattern matching, and palindrome problems.

General Recognition Cues
General indicators that this pattern might be applicable
  • Pattern search
  • All occurrences
  • Palindrome centers
Pattern Variants & Approaches
Different methodologies and implementations for this pattern
1

KMP

Prefix function / lps table

When to Use This Variant
  • Avoid re-scan
Use Case
Substring search
Advantages
  • O(n+m)
  • Deterministic
Implementation
def kmp_search(s, p):
    # build lps
    lps=[0]*len(p); k=0
    for i in range(1,len(p)):
        while k>0 and p[k]!=p[i]: k=lps[k-1]
        if p[k]==p[i]: k+=1; lps[i]=k
    # search
    j=0; res=[]
    for i,ch in enumerate(s):
        while j>0 and p[j]!=ch: j=lps[j-1]
        if p[j]==ch: j+=1
        if j==len(p): res.append(i-j+1); j=lps[j-1]
    return res
2

Z-Algorithm

Z-boxes for prefix matches

When to Use This Variant
  • Z array
Use Case
Pattern locations
Advantages
  • O(n)
  • Simple linear
Implementation
def z_array(s):
    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
3

Rolling Hash

Rabin–Karp style hashes

When to Use This Variant
  • Substrings compare
Use Case
Detect matching substrings
Advantages
  • Average linear
  • Supports set lookups
Implementation
def rabin_karp(s, p):
    base, mod = 911382323, 10**9+7
    n, m = len(s), len(p)
    if m>n: return []
    powB=[1]*(n+1)
    for i in range(1,n+1): powB[i]=(powB[i-1]*base)%mod
    def h(ss):
        x=0
        for ch in ss: x=(x*base + ord(ch))%mod
        return x
    hp=h(p); hs=h(s[:m])
    res=[]
    if hs==hp: res.append(0)
    for i in range(m, n):
        hs=( (hs*base - ord(s[i-m])*powB[m]) + ord(s[i]) )%mod
        if hs==hp: res.append(i-m+1)
    return res
4

Manacher

Linear-time longest palindrome

When to Use This Variant
  • Center expansion with arms
Use Case
Longest palindromic substring
Advantages
  • O(n)
  • Elegant
Implementation
def manacher(s):
    A='|'+'|'.join(s)+'|'
    Z=[0]*len(A); L=R=0; best=0
    for i in range(len(A)):
        if i<R: Z[i]=min(R-i, Z[2*L-i])
        while i-Z[i]-1>=0 and i+Z[i]+1<len(A) and A[i-Z[i]-1]==A[i+Z[i]+1]: Z[i]+=1
        if i+Z[i]>R: L=i; R=i+Z[i]
        best=max(best, Z[i])
    return best
Common Pitfalls
Watch out for these common mistakes
  • Indexing failure function
  • Hash collisions handling
  • Even/odd centers in Manacher
Code Templates
Compare implementations across different languages
def template(*args, **kwargs):
    # General template placeholder
    pass
Example Problems
Classic LeetCode problems using this pattern
Complexity Analysis
Time Complexity
O(n)

Per algorithm typical bound.

Space Complexity
O(n)

Aux arrays/hashes.

Ready to test your knowledge?

Test your pattern recognition with interactive questions