Advanced String Algorithms: Z, Rabin-Karp & Suffix Arrays

KMP is the first serious string algorithm most people learn. But the world of string algorithms is vast: there are algorithms for rolling hashes, multi-pattern matching, palindrome detection, and suffix-based searching. Each solves a different class of problem more elegantly or efficiently than the alternatives. This post gives you six algorithms and a clear decision framework for when to use each.

1. The Z-Algorithm — Pattern Matching via Z-Array

The Z-array of a string s is defined as: Z[i] = length of the longest substring starting at s[i] that matches a prefix of s.

String: a  a  b  x  a  a  b
Index:  0  1  2  3  4  5  6
Z:      -  1  0  0  3  1  0
Z[1] = 1: s[1..1] = “a” matches prefix “a”
Z[4] = 3: s[4..6] = “aab” matches prefix “aab”

The efficient O(n) construction

The key idea is maintaining a “Z-box” [l, r] — the rightmost interval where s[l..r] matches a prefix. When processing s[i], if i falls inside the current Z-box, you can reuse previously computed Z-values.

def z_function(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

Pattern matching with Z-algorithm

Concatenate pattern + "$" + text (where $ does not appear in either) and compute the Z-array. Any position i where Z[i] == len(pattern) is a match.

def z_search(text, pattern):
    combined = pattern + "$" + text
    z = z_function(combined)
    m = len(pattern)
    matches = []
    for i in range(m + 1, len(combined)):
        if z[i] == m:
            matches.append(i - m - 1)
    return matches

print(z_search("aabxaabxaab", "aab"))  # [0, 4, 8]

Time: O(n + m). Same complexity as KMP, but many find the Z-algorithm more intuitive — the Z-array directly tells you “how far does this position match the beginning?“

2. Rabin-Karp — Rolling Hash for Substring Search

Rabin-Karp uses a hash function to avoid character-by-character comparison. Compute the hash of the pattern, then slide a window across the text, updating the hash in O(1) using the “rolling” property.

def rabin_karp(text, pattern, base=31, mod=10**9 + 7):
    n, m = len(text), len(pattern)
    if m > n:
        return []

    # Precompute base^m
    power = pow(base, m, mod)

    # Hash of pattern
    pat_hash = 0
    for ch in pattern:
        pat_hash = (pat_hash * base + ord(ch)) % mod

    # Hash of first window
    win_hash = 0
    for ch in text[:m]:
        win_hash = (win_hash * base + ord(ch)) % mod

    matches = []
    for i in range(n - m + 1):
        if i > 0:
            # Roll the hash: remove leftmost char, add new rightmost char
            win_hash = (win_hash * base - ord(text[i-1]) * power + ord(text[i+m-1])) % mod

        if win_hash == pat_hash:
            # Verify to avoid hash collision
            if text[i:i+m] == pattern:
                matches.append(i)

    return matches

print(rabin_karp("abracadabra", "abra"))  # [0, 7]

Average case: O(n + m). Worst case: O(nm) due to hash collisions, but with a good hash and modulus, collisions are rare.

When Rabin-Karp shines: searching for multiple patterns of the same length (compute hash once for each pattern, store in a set).

3. Suffix Arrays — Space-Efficient Suffix Structure

A suffix array is a sorted array of all suffixes of a string, represented by their starting indices. It gives you the power of a suffix tree with much less memory.

def build_suffix_array(s):
    n = len(s)
    suffixes = sorted(range(n), key=lambda i: s[i:])
    return suffixes

s = "banana"
sa = build_suffix_array(s)
# Suffixes sorted:
# 5: "a"
# 3: "ana"
# 1: "anana"
# 0: "banana"
# 4: "na"
# 2: "nana"
print(sa)  # [5, 3, 1, 0, 4, 2]

The naive construction above is O(n^2 log n). In practice, you use the DC3/SA-IS algorithm for O(n) construction, or the O(n log n) prefix-doubling approach:

def build_suffix_array_fast(s):
    """O(n log^2 n) construction using prefix doubling."""
    n = len(s)
    sa = list(range(n))
    rank = [ord(c) for c in s]
    tmp = [0] * n

    k = 1
    while k < n:
        def compare(a, b):
            if rank[a] != rank[b]:
                return rank[a] - rank[b]
            ra = rank[a + k] if a + k < n else -1
            rb = rank[b + k] if b + k < n else -1
            return ra - rb

        from functools import cmp_to_key
        sa.sort(key=cmp_to_key(compare))

        tmp[sa[0]] = 0
        for i in range(1, n):
            tmp[sa[i]] = tmp[sa[i-1]] + (1 if compare(sa[i-1], sa[i]) < 0 else 0)
        rank = tmp[:]
        k *= 2

    return sa

Using suffix arrays for pattern matching

Binary search on the suffix array to find all occurrences of a pattern in O(m log n):

def search_suffix_array(text, sa, pattern):
    n, m = len(text), len(pattern)
    lo, hi = 0, n - 1

    # Find leftmost match
    while lo < hi:
        mid = (lo + hi) // 2
        if text[sa[mid]:sa[mid]+m] < pattern:
            lo = mid + 1
        else:
            hi = mid
    left = lo

    hi = n - 1
    while lo < hi:
        mid = (lo + hi + 1) // 2
        if text[sa[mid]:sa[mid]+m] > pattern:
            hi = mid - 1
        else:
            lo = mid
    right = lo

    if text[sa[left]:sa[left]+m] == pattern:
        return [sa[i] for i in range(left, right + 1)]
    return []

The LCP array (Longest Common Prefix between consecutive suffixes in sorted order) pairs with the suffix array to answer many substring problems: count distinct substrings, find the longest repeated substring, etc.

4. Aho-Corasick — Multiple Pattern Matching

KMP and Z-algorithm match one pattern at a time. Aho-Corasick matches multiple patterns simultaneously in O(n + m + z) where z is the number of matches — it processes the text once regardless of how many patterns there are.

It builds a trie of all patterns, adds failure links (like KMP’s failure function but on a trie), and processes the text character by character.

from collections import deque, defaultdict

class AhoCorasick:
    def __init__(self):
        self.goto = [{}]       # trie transitions
        self.fail = [0]        # failure links
        self.output = [[]]     # output at each node (pattern indices)
        self.state_count = 1

    def add_pattern(self, pattern, index):
        state = 0
        for ch in pattern:
            if ch not in self.goto[state]:
                self.goto[state][ch] = self.state_count
                self.goto.append({})
                self.fail.append(0)
                self.output.append([])
                self.state_count += 1
            state = self.goto[state][ch]
        self.output[state].append(index)

    def build(self):
        queue = deque()
        # All depth-1 nodes fail to root
        for ch, s in self.goto[0].items():
            queue.append(s)

        while queue:
            u = queue.popleft()
            for ch, v in self.goto[u].items():
                queue.append(v)
                # Follow failure links to find longest proper suffix
                f = self.fail[u]
                while f and ch not in self.goto[f]:
                    f = self.fail[f]
                self.fail[v] = self.goto[f].get(ch, 0)
                if self.fail[v] == v:
                    self.fail[v] = 0
                self.output[v] = self.output[v] + self.output[self.fail[v]]

    def search(self, text):
        state = 0
        results = []
        for i, ch in enumerate(text):
            while state and ch not in self.goto[state]:
                state = self.fail[state]
            state = self.goto[state].get(ch, 0)
            for pattern_idx in self.output[state]:
                results.append((i, pattern_idx))
        return results

ac = AhoCorasick()
patterns = ["he", "she", "his", "hers"]
for i, p in enumerate(patterns):
    ac.add_pattern(p, i)
ac.build()

matches = ac.search("ahishers")
print(matches)
# [(3, 2), (4, 0), (4, 1), (7, 0), (7, 3)]
# "his" at 1, "he" at 3, "she" at 3, "he" at 6, "hers" at 4

Real-world uses: virus scanning (match thousands of malware signatures against file content), network intrusion detection (Snort), and text filtering.

5. Manacher’s Algorithm — All Palindromes in O(n)

Finding the longest palindromic substring naively is O(n^2) (expand around each centre). Manacher’s algorithm does it in O(n) by reusing previously computed palindrome information.

The trick: insert a special character between every pair of characters to handle even-length palindromes uniformly.

def manacher(s):
    # Transform: "abc" -> "^#a#b#c#$"
    t = "^#" + "#".join(s) + "#$"
    n = len(t)
    p = [0] * n  # p[i] = radius of palindrome centred at i in t

    c = r = 0  # centre and right boundary of rightmost palindrome

    for i in range(1, n - 1):
        mirror = 2 * c - i
        if i < r:
            p[i] = min(r - i, p[mirror])
        # Try to expand
        while t[i + p[i] + 1] == t[i - p[i] - 1]:
            p[i] += 1
        # Update centre if expanded past r
        if i + p[i] > r:
            c, r = i, i + p[i]

    # Find longest
    max_len = max(p)
    center_idx = p.index(max_len)
    start = (center_idx - max_len) // 2
    return s[start:start + max_len]

print(manacher("babad"))     # "bab" or "aba"
print(manacher("cbbd"))      # "bb"
print(manacher("racecar"))   # "racecar"

Why it works: when position i is inside a known palindrome centred at c, the palindrome at i’s mirror position gives us a lower bound for p[i]. We only need to expand beyond what the mirror already tells us.

6. String Hashing — O(1) Substring Comparison

Precompute hash values for all prefixes using polynomial hashing. Then compare any two substrings in O(1) by computing their hash from prefix hashes.

class StringHasher:
    def __init__(self, s, base=31, mod=10**9 + 7):
        self.mod = mod
        self.base = base
        n = len(s)

        self.h = [0] * (n + 1)      # prefix hashes
        self.pw = [1] * (n + 1)     # powers of base

        for i in range(n):
            self.h[i+1] = (self.h[i] * base + ord(s[i])) % mod
            self.pw[i+1] = (self.pw[i] * base) % mod

    def get_hash(self, l, r):
        """Hash of s[l..r] (inclusive)."""
        return (self.h[r+1] - self.h[l] * self.pw[r - l + 1]) % self.mod

# Usage: check if two substrings are equal in O(1)
hasher = StringHasher("abcabcabc")
print(hasher.get_hash(0, 2) == hasher.get_hash(3, 5))  # True: "abc" == "abc"
print(hasher.get_hash(0, 2) == hasher.get_hash(1, 3))  # False: "abc" != "bca"

Double hashing (use two independent hash functions) reduces collision probability to near zero:

class DoubleHasher:
    def __init__(self, s):
        self.h1 = StringHasher(s, base=31, mod=10**9 + 7)
        self.h2 = StringHasher(s, base=37, mod=10**9 + 9)

    def get_hash(self, l, r):
        return (self.h1.get_hash(l, r), self.h2.get_hash(l, r))

Applications: longest common substring (binary search + hashing), counting distinct substrings, and checking palindromes (compare substring hash with its reverse hash).

When to Use Which Algorithm

Decision flowchart

1. How many patterns? One → KMP/Z. Multiple → Aho-Corasick or Rabin-Karp.
2. Need palindromes? → Manacher’s.
3. Need to compare many substrings? → String hashing.
4. Need all suffixes or complex substring queries? → Suffix array.

Recap

String algorithms are about choosing the right tool:

• Z-algorithm is KMP’s intuitive twin — same power, clearer mental model
• Rabin-Karp excels when you have multiple patterns of the same length
• Suffix arrays give you the power of suffix trees with less memory
• Aho-Corasick is the multi-pattern matching powerhouse
• Manacher’s finds palindromes in linear time
• String hashing is the Swiss army knife for O(1) substring operations

Each algorithm has a specific niche. Learn to recognise which niche your problem falls into, and the right algorithm becomes obvious.

Next steps

For more advanced data structure techniques, see Advanced Tree Algorithms and Competitive Programming Patterns.

Questions or feedback? Email codeloomdevv@gmail.com.