CodeMosa

Master LeetCode Patterns

AdvancedAdvanced Patterns

String Algorithms

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

Time: O(n)
Space: O(n)

What is String Algorithms?

#
Definition: Use prefix tables (KMP/Z), rolling hashes, or center expansion (Manacher) for linear-time string operations.

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.

How String Algorithms works

#

KMP/Z for linear-time matching, rolling hash for substring checks, and Manacher's algorithm for palindromic substrings.

  • Pattern search
  • All occurrences
  • Palindrome centers

General Recognition Cues

#
General indicators that this pattern might be applicable
  • Pattern search
  • All occurrences
  • Palindrome centers

Related Collections

#
Curated practice sets for this pattern
KMP Practice Problems

Code Templates

#
KMP/Z for linear-time matching, rolling hash for substring checks, and Manacher's algorithm for palindromic substrings.
# Range Queries (Fenwick/BIT) Template
class Fenwick:
    def __init__(self, n): self.n=n; self.bit=[0]*(n+1)
    def add(self, i, delta):
        i+=1
        while i<=self.n:
            self.bit[i]+=delta; i += i & -i
    def sum(self, i):
        i+=1; s=0
        while i>0:
            s+=self.bit[i]; i -= i & -i
        return s
    def range_sum(self, l, r): return self.sum(r)-self.sum(l-1)

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

Related Patterns

#
BacktrackingFenwick Tree (Binary Indexed Tree)GreedyKMP AlgorithmMath & BitsRange Queries

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