String Algorithms (KMP, Z, Rolling Hash, Trie)

String Algorithms (KMP, Z, Rolling Hash, Trie) | Algoryva

Intuition

Finding a phrase in a book without re-reading

You are looking for the phrase “abcabd” in a long text and you have matched “abcab” when the next letter turns out to be wrong. A careless search goes back to the second letter of the text and starts over, re-reading characters it has already seen. But you *know* what those characters were: you matched them! The pattern's own shape tells you how much of what you matched can still be part of a new match, and where to carry on.

String algorithms are about not forgetting what you have already learned: KMP and the Z-function reuse matched characters, hashing summarises a substring in one number, and a trie shares the common beginning of many words.

First, the naive way

Try every starting position

The direct way places the pattern at every position of the text and compares character by character until a mismatch.

The comparison counter shows the cost: 14 comparisons for a 9-character text. But for a text of 1,000 letters a and a pattern of 500 as followed by a b, every one of the 500 starting positions matches 500 letters before failing on the last one: 250,500 comparisons, almost all of them re-reading characters already seen.

python

def find_all_naive(text, pat):
    n, m = len(text), len(pat)
    hits, comparisons = [], 0
    for i in range(n - m + 1):
        j = 0
        while j < m:
            comparisons += 1
            if text[i + j] != pat[j]:
                break
            j += 1
        if j == m:
            hits.append(i)
    return hits, comparisons

print(find_all_naive("abcabcabd", "abcabd"))   # ([3], 14)
print(find_all_naive("a" * 1000, "a" * 500 + "b"))   # ([], 250500)

Cost: O(n × m): n starting positions, up to m comparisons each. About 10¹⁰ for n = m/2 = 10⁵.

The observation

A mismatch after j matched characters teaches you what to do next

Suppose the first j characters of the pattern matched the text, then a mismatch occurs. Those j text characters equal pattern[0..j-1]. A new match could only start at a position where a suffix of that matched part equals a prefix of the pattern. The longest such overlap (a border) is exactly what tells you the next best alignment, and it depends only on the pattern, not on the text.

Precompute the border length for every prefix of the pattern (the prefix function). Then on a mismatch you slide the pattern right so that the border lines up, without moving the text pointer backwards. Each text character is looked at O(1) times in total.

The concept

The four tools

Each solves a slightly different problem. Learn what each is *for*.

Prefix function (π) and KMP: π[i] = the length of the longest proper prefix of s[0..i] that is also a suffix of it (a *border*). KMP search uses π to match a pattern in O(n + m). π also gives periods and borders of a string.
Z-function: z[i] = the length of the longest common prefix of s and the suffix starting at i. Same power as π (they can be converted into each other), often easier to reason about for “how far does the prefix match here?”.
Rolling hash (Rabin–Karp): treat a string as a number in some base, modulo a large number, so a substring has a hash that can be updated in O(1) when the window slides. Compares substrings fast, but two different strings can share a hash (a collision), so a match is usually verified.
Trie (prefix tree): a tree with one edge per letter; words with the same beginning share a path. Supports insert, exact search and prefix queries in time proportional to the word length, not the number of words.
Border: a proper prefix that is also a suffix (for “abacaba” the borders have lengths 3 and 1). A string of length n has period n − (longest border) (and repeats exactly when that divides n).

See it move

Building the prefix function

The top row is the pattern, the second row the prefix function as it is filled in. The pointer j is the current border length: if the next character extends it, j grows; if not, we fall back to a shorter border (j = π[j − 1]) and try again. Watch how falling back reuses earlier answers instead of restarting.

See it move

KMP search: the text pointer never moves back

The top row is the text; the second row shows the pattern placed at its current alignment. Green text boxes are matched so far. At the mismatch the pattern slides right (its offset changes) while the text pointer stays put. Compare this with the naive method, which would restart one position after the previous start.

Worked by hand

The prefix function by hand

Pattern abacaba (positions 0 to 6). π[i] is the longest border of the prefix ending at i.

i	prefix s[0..i]	longest proper border	π[i]
0	a	none	0
1	ab	none	0
2	aba	a	1
3	abac	none	0
4	abaca	a	1
5	abacab	ab	2
6	abacaba	aba	3

1
How i = 5 and 6 are found fast
At i = 4 the border was 1 (“a”). At i = 5 the next letter 'b' equals s[1], so the border grows to 2 (“ab”). At i = 6 the letter 'a' equals s[2], so it grows to 3 (“aba”). No re-comparison of earlier letters was needed.

Implementation

The prefix function in code

The loop keeps k, the length of the current border. When the next character fails to extend it, k falls back through shorter and shorter borders.

Plan in plain steps

pseudocode

pi[0] = 0; k = 0
for i from 1 to n − 1:
    while k > 0 and s[i] != s[k]: k = pi[k − 1]
    if s[i] == s[k]: k += 1
    pi[i] = k

python

def prefix_function(s):
    pi = [0] * len(s)
    k = 0
    for i in range(1, len(s)):
        while k > 0  s[i] != s[k]:
            k = pi[k - ]               
         s[i] == s[k]:
            k += 
        pi[i] = k
     pi

(())   
(())   
(())   
(())

Implementation

KMP search, checked against brute force

Searching is the same loop run over the text, using π of the pattern. When all m characters have matched, record the match and fall back to the pattern's own longest border so overlapping matches are found.

python

def prefix_function(s):
    pi = [0] * len(s)
    k = 0
    for i in range(1, len(s)):
        while k > 0 and s[i] != s[k]:
            k = pi[k - 1]               # fall back to the next shorter border
        if s[i] == s[k]:
            k += 1
        pi[i] = k
     pi

 (text, pat):
    pi = (pat)
    hits, k = [], 
     i, ch  (text):
         k >   ch != pat[k]:
            k = pi[k - ]               
         ch == pat[k]:
            k += 
         k == (pat):
            hits.(i - k + )
            k = pi[k - ]               
     hits

((, ))   
((, ))   
((, ))   
((, ))   

 random
random.()
ok = 
 _  ():
    text = .(random.()  _  (random.(, )))
    pat = .(random.()  _  (random.(, )))
    brute = [i  i  ((text) - (pat) + )  text[i:i + (pat)] == pat]
    ok = ok  (text, pat) == brute
(ok)

Implementation

The Z-function

z[i] is how far the prefix of s matches the text starting at i. The trick is to keep a window [l, r) where a prefix match was last found: positions inside it are copies of earlier positions, so part of their answer is already known.

python

def z_function(s):
    n = len(s)
    z = [0] * n
    l = r = 0                            # [l, r) is the rightmost match of a prefix seen so far
    for i in range(1, n):
        if i < r:
            z[i] = min(r - i, z[i - l])  # reuse what we already know
        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 (text, pat):
    s = pat +  + text                 
    z = (s)
     [i - (pat) -   i, v  (z)  v == (pat)]

(())   
((, ))   
((, ))

Implementation

A rolling hash

Treat a string as a number: hash(s) = s[0]·b^(m−1) + … + s[m−1] modulo a large prime. Sliding the window one place is arithmetic: remove the leading character's contribution, shift everything up one base power, add the new character. That is O(1) per slide, so every window's hash costs O(n) in total.

python

def poly_hash(s, base=131, mod=(1 << 61) - 1):
    h = 0
    for ch in s:
        h = (h * base + ord(ch)) % mod
    return h

def rolling_find(text, pat, base=131, mod=(1 << 61) - 1):
    n, m = (text), (pat)
     m > n:
         []
    power = (base, m - , mod)
    hp = (pat, base, mod)
    h = (text[:m], base, mod)
    hits = []
     i  (n - m + ):
         h == hp  text[i:i + m] == pat:     
            hits.(i)
         i + m < n:
            h = ((h - (text[i]) * power) * base + (text[i + m])) % mod
     hits

(((ord, )) == ((ord, )), () == ())   
((, ))   
((, ))   
((, ))   

 random
random.()
ok = 
 _  ():
    text = .(random.()  _  (random.(, )))
    pat = .(random.()  _  (random.(, )))
    brute = [i  i  ((text) - (pat) + )  text[i:i + (pat)] == pat]
    ok = ok  (text, pat) == brute
(ok)

See it move

A trie of words

Words are inserted letter by letter, following existing nodes where possible and creating new ones where not. Notice that car, cart and cat share the start ca. Green nodes mark where a word ends. The look-ups at the end show the difference between a stored word (cat), a mere prefix (ca) and a missing word (cow).

Implementation

A trie class

Each node holds a dictionary from letter to child, a flag marking the end of a word, and a counter of words passing through.

python

class Trie:
    def __init__(self):
        self.children = {}
        self.end = False
        self.count = 0                   # how many inserted words pass through this node

    def insert(self, word):
        node = self
        node.count += 1                  # the root is passed through by every word
        for ch in word:
            node = node.children.setdefault(ch, Trie())
            node.count += 1
        node.end = 

     (self, s):
        node = self
         ch  s:
            node = node.children.(ch)
             node  :
                 
         node

     (self, word):
        node = self.(word)
         node     node.end

     (self, prefix):
         self.(prefix)   

     (self, prefix):
        node = self.(prefix)
         node.count  node  

t = ()
 w  [, , , ]:
    t.(w)
(t.(), t.(), t.())   
(t.(), t.())   
(t.(), t.(), t.(), t.())

Complexity

Costs

All four turn an O(n × m) re-reading problem into a single pass. Choose by the question: *where does a pattern occur?* → KMP or Z; *are these two substrings equal?* (many times) → hashing; *which stored words start with this?* → trie.

Naive substring search

time O(n × m)space O(1)

Up to m comparisons at each of n starting positions.

KMP (prefix function + scan)

time O(n + m)space O(m)

The pattern pointer's total fall-backs are bounded by its total increases.

Z-function (and search via pattern#text)

time O(n + m)space O(n + m)

Each character beyond the window is examined once.

Rolling hash search

time O(n + m) expectedspace O(1) extra

One O(1) hash update per window, plus a verification only on hash matches.

Trie insert / search / prefix query

time O(length of the word)space O(total characters)

One step per letter; storage is one node per distinct prefix.

Trie memory in Python

time -space large constant

A dictionary per node is heavy; for a small alphabet use arrays of 26 children, or a sorted list with binary search.

Edge cases

Empty patternIt matches everywhere or nowhere depending on the statement. The code here assumes a non-empty pattern (pat[k] would fail on an empty one). Handle it before calling.
Pattern longer than the textNo match. KMP returns [] naturally; the rolling-hash version returns early.
Overlapping matchesAfter a full match fall back with k = pi[k - 1], not k = 0, or you will miss matches like aa in aaaaa.
All characters equalπ is [0, 1, 2, …]. The naive search is at its worst here, while KMP stays linear.
Separator in the Z-search stringUse a character that appears in neither string, or a match could straddle the join.
Hash collisions and adversarial testsUse a large modulus (such as 2⁶¹ − 1), a random base, and verify matches (or use two moduli).
Case, spaces and UnicodeStrings compare by code point. Normalise case if the statement asks for case-insensitive matching.

Common mistakes

Mistakes to avoid

Resetting to k = 0 after a full match in KMP.
Use k = pi[k - 1] so overlapping matches are found.
Using the sum of character codes (or any order-blind value) as a hash.
Use a polynomial hash so position matters.
Trusting a hash match without checking, with a small modulus.
Verify the substring or use a 61-bit modulus (or two moduli) and a random base.
Confusing a border with a suffix equal to the whole string.
A border is a proper prefix (shorter than the string) that is also a suffix.
Treating a trie search as a prefix check.
search needs the end-of-word flag; starts_with does not.

Recognize it in a contest

How to spot a string-algorithm problem

Reach for it when the problem says or implies

“Find all occurrences of a pattern in a text” with lengths up to 10⁵ or 10⁶: KMP or Z (or hashing).
“Border, period, repeated substring, shortest string that builds this one by repetition”: the prefix function.
“Compare many substrings for equality” or “count distinct substrings of a given length”: hashing.
“How many dictionary words start with this prefix?”, autocomplete, longest common prefix of many words: a trie.
Words sharing beginnings, a dictionary with lookups by prefix, word games (boggle, word search with pruning): trie plus backtracking.
“Longest prefix that is also a suffix”: π of the last position.

Look elsewhere when

Worked problem

The shortest repeating unit of a string

The problem

Given a string s, find the length of the shortest string t such that s is t repeated whole times. (If s is not a repetition of anything shorter, the answer is the length of s.)

Compute the prefix function. Its last value is the longest border of the whole string.
If the border has length b, then s has a period of p = n − b (shifting by p lines the string up with itself).
The string is made of whole repeats exactly when p divides n. Otherwise the shortest repeating unit is the whole string.

python

def prefix_function(s):
    pi = [0] * len(s)
    k = 0
    for i in range(1, len(s)):
        while k > 0 and s[i] != s[k]:
            k = pi[k - 1]               # fall back to the next shorter border
         s[i] == s[k]:
            k += 
        pi[i] = k
     pi

 (s):
    p = (s) - (s)[-]
     p  (s) % p ==   (s)

 (s):
     (s)[-]

(())   
(())   
(())   
(())   
((), (), ())   
((( * k)[:] ==  * k  ( * k) ==   k  (, )))

Worked problem

Count the words with a given prefix

The problem

Given a list of words (duplicates allowed) and a list of queries, for each query print how many of the words start with it (the empty query matches every word).

Checking every word for every query is O(words × queries × length).
Insert all words into a trie, and keep at every node the number of words that pass through it.
A query walks down its letters. If a letter is missing, the answer is 0; otherwise it is the count stored at the last node.

python

class Trie:
    def __init__(self):
        self.children = {}
        self.count = 0

    def insert(self, word):
        node = self
        node.count += 1                  # the root is passed through by every word
        for ch in word:
            node = node.children.setdefault(ch, ())
            node.count += 

     (self, prefix):
        node = self
         ch  prefix:
            node = node.children.(ch)
             node  :
                 
         node.count

 (words, queries):
    t = ()
     w  words:
        t.(w)
     [t.(q)  q  queries]

words = [, , , , , ]
((words, [, , , , , , ]))   
((words, [, , , , , , ]) == [(w.(q)  w  words)  q  [, , , , , , ]])

Wrap-up

Remember this

Naive search re-reads characters after every mismatch, costing O(n × m).
The prefix function stores the longest border of every prefix; KMP uses it to slide the pattern while the text pointer only moves forward: O(n + m).
The Z-function gives the same power and can search via pattern + separator + text.
A polynomial rolling hash updates a window's hash in O(1); equal hashes should be verified, and the base chosen randomly.
A trie shares common prefixes, giving insert, search and prefix queries in time proportional to the word length.

Cheat sheet

Prefix function: π[i] = longest proper border of s[0..i]; while k > 0 and s[i] != s[k]: k = π[k−1]
KMP search: same loop over the text; on k == m record a match, then k = π[m−1]
Z-function: z[i] = common prefix of s and s[i:]; search via pattern + '#' + text
Rolling hash: h = (h − c_old·b^(m−1))·b + c_new (mod p); verify matches
Trie: children dict + end flag + pass-through count; ops cost O(word length)
Cost: KMP, Z: O(n + m) · hash: O(n + m) expected · naive: O(n·m)

Top traps to avoid

Resetting to k = 0 after a full match in KMP.
Using the sum of character codes (or any order-blind value) as a hash.
Trusting a hash match without checking, with a small modulus.

Mastery check

0 of 15 answered

Answer from understanding, not memory of the page. You need 12 of 15. Each answer is explained, and you can retry as often as you like.

1.Why is KMP O(n + m) rather than O(n × m)?
2.What is the prefix function of "aabaaab"?
3.After KMP finds a full match, why set k = pi[k - 1] instead of k = 0?
4.Why is the sum of character codes a poor string hash?
5.“Answer many queries of the form: how many dictionary words start with this prefix?” suggests:
6.What is the shortest repeating unit length of "abcabcabc", using the longest border?
7.KMP prefix function for s = 'aabaaab'. What is printed?
8.Count overlapping occurrences of 'aba' in 'ababa'. What is printed?
9.How many distinct non-empty substrings does 'aa' have?
10.A trie gets the words 'cat' and 'car'. Counting every node including the root, how many nodes are there?
11.What does the KMP prefix function store for each position?
12.What is the running time of KMP to search a pattern of length m in a text of length n?
13.Why must a rolling-hash match be verified?
14.Longest palindromic substring of 'babad' (length only). What is printed?
15.Which structure is best for many prefix searches over a dictionary of words?

Slicing in a hot loop (text[i:i + m] for every i).

String Algorithms (KMP, Z, Rolling Hash, Trie)

After this lesson you will be able to

Builds on

Unlocks

Finding a phrase in a book without re-reading

Try every starting position

A mismatch after j matched characters teaches you what to do next

The four tools

Building the prefix function

KMP search: the text pointer never moves back

The prefix function by hand

The prefix function in code

KMP search, checked against brute force

The Z-function

A rolling hash

A trie of words

A trie class

Costs

Edge cases

Mistakes to avoid

How to spot a string-algorithm problem

The shortest repeating unit of a string

Count the words with a given prefix

Wrap-up

Remember this

Cheat sheet

Top traps to avoid

Mastery check

Practice this topic

Core60 problems

Reading the code

Reading the code

Reading the code

Reading the code

Reading the code