Skip to content
Hari KharelStudy

String algorithms

advancedCommon atGoogleMetatrading firmsRead firstString manipulationTwo pointersPractise in the Sandbox →

Naive matching re-reads text after every mismatch: O(n·m) worst case. KMP precomputes the pattern’s prefix function π (for each position, the longest border: a proper prefix that is also a suffix) so that after a mismatch the pattern shifts by the right amount and the text pointer never moves back: O(n + m). The Z-function gives the same power from a different angle. Rolling hashes trade the worst-case guarantee for simplicity and flexibility.

The idea in plain words

Section titled “The idea in plain words”

You’re searching for aabaaab and have matched aabaa when the next character disagrees. The naive method slides the pattern one place right and starts comparing from scratch, re-reading four characters it has already seen.

But you already know those characters: they are aabaa, the start of your own pattern. So the question “where could the next match start?” can be answered from the pattern alone, before you ever see the text: the longest suffix of aabaa that is also a prefix of the pattern is aa. Slide so that aa lines up, and continue comparing from the third pattern character. No text character is read twice.

That “longest proper prefix that is also a suffix” is called a border. The prefix function stores the border length for every prefix of the pattern:

i 0 1 2 3 4 5 6
p[i] a a b a a a b
π[i] 0 1 0 1 2 2 3

See it

Section titled “See it”

Start with Failure function π and watch k fall back through shorter borders. Then switch to Naive vs KMP: run both on the same text and compare the comparison counters. Last, the Z-function with its [l, r) box.

Prefix function, KMP search and the Z-function
step through
k
a
a
b
a
a
a
b
0123456
i
0
·
·
·
·
·
·
π (border length)
π[0]0
i: char being addedcurrent border (prefix and suffix)p[k]: compared with p[i]
π[i] = length of the longest proper prefix of p[0..i] that is also a suffix of it. A single character has no proper border: π[0] = 0.
1 / 16

When to reach for it

Section titled “When to reach for it”
The problem says… Tool
“find all occurrences of a pattern”, with worst-case linear time required KMP (prefix function) or Z-function.
“is the string made of a repeated block?”, “shortest period” Prefix function: period = n − π[n−1].
“longest prefix that is also a suffix”, “shortest palindrome by adding in front” Prefix function on a cleverly built string.
“for each position, how much matches the start?” Z-function.
many patterns at once Trie + Aho-Corasick (KMP generalised to a trie).
compare many substrings for equality, or substrings of a fixed length Rolling hash.
“longest repeated / common substring” over large inputs Suffix array or suffix automaton, or hashing plus another idea.
short strings, one-off search The language’s built-in find / indexOf / IndexOf is fine. Say so.

How it works

Section titled “How it works”

Prefix function

Section titled “Prefix function”
  1. Start with k = π[i−1]: the border of the previous prefix is the only candidate to extend.
  2. While p[i] ≠ p[k] and k > 0, fall back to the next-shorter border: k = π[k−1].
  3. If p[i] = p[k], the border grows by one: k += 1. Store π[i] = k.
  4. Applications read π afterwards, e.g. the period of the whole string is n − π[n−1].
prefix_function.py
def prefix_function(s: str) -> list[int]:
    """pi[i] = length of the longest proper prefix of s[:i+1] that is also its suffix."""
    pi = [0] * len(s)
    for i in range(1, len(s)):
        k = pi[i - 1]                    # 1. start from the previous border
        while k > 0 and s[i] != s[k]:
            k = pi[k - 1]                # 2. fall back to the next-shorter border
        if s[i] == s[k]:
            k += 1                       # 3. extend the border by one character
        pi[i] = k
    return pi




def shortest_period(s: str) -> int:
    """Length of the shortest block that, repeated, builds s ("abab" -> 2)."""
    if not s:
        return 0
    p = len(s) - prefix_function(s)[-1]  # 4. the longest border leaves the period
    return p if len(s) % p == 0 else len(s)




if __name__ == "__main__":
    assert prefix_function("aabaaab") == [0, 1, 0, 1, 2, 2, 3]
    assert prefix_function("abcabcd") == [0, 0, 0, 1, 2, 3, 0]
    assert prefix_function("") == []
    assert shortest_period("abababab") == 2
    assert shortest_period("abcab") == 5     # not a whole number of repeats
    assert shortest_period("zzzz") == 1
    print("ok")

Searching with π follows the same loop, with the text in place of the pattern’s own suffix: keep j = number of pattern characters matched; on a mismatch fall back with j = π[j−1]; on a full match report it and fall back the same way so overlapping matches are found. The visualization shows every step. A common shortcut is to run the prefix function on pattern + '#' + text (with a separator that appears in neither) and look for positions where π equals the pattern length.

Z-function

Section titled “Z-function”

z[i] is the length of the longest substring starting at i that equals a prefix of the string. It’s computed left to right while remembering the Z-box [l, r): the match found so far that reaches furthest right.

  1. If i is inside the box, s[i..r) is a copy of s[i−l..r−l), so start from min(r − i, z[i − l]) for free.
  2. Extend by direct comparison past what’s known.
  3. If the match now reaches past r, move the box to [i, i + z[i]).
z_function.py
def z_function(s: str) -> list[int]:
    """z[i] = length of the longest common prefix of s and s[i:]. z[0] is set to len(s)."""
    n = len(s)
    z = [0] * n
    if n:
        z[0] = n
    left = right = 0                         # [left, right) = rightmost match found so far
    for i in range(1, n):
        if i < right:
            z[i] = min(right - i, z[i - left])   # 1. inside the box: reuse the mirror value
        while i + z[i] < n and s[z[i]] == s[i + z[i]]:
            z[i] += 1                        # 2. extend by direct comparison
        if i + z[i] > right:
            left, right = i, i + z[i]        # 3. the box moves right (never left)
    return z




if __name__ == "__main__":
    assert z_function("aabxaabxcaab") == [12, 1, 0, 0, 4, 1, 0, 0, 0, 3, 1, 0]
    assert z_function("aaaaa") == [5, 4, 3, 2, 1]
    assert z_function("") == []
    print("ok")

What it costs

Section titled “What it costs”
Preprocess Search Extra space
Naive none O(n·m) worst (e.g. text aaaa…a, pattern aa…ab) O(1)
KMP O(m) prefix function O(n): the text pointer never moves back O(m)
Z-function on p + sep + t O(n + m) O(n + m)
Rabin-Karp (rolling hash) O(m) O(n + m) expected, O(n·m) worst if every hit is verified O(1)
Built-in find / indexOf implementation-defined; fast in practice

Why π is linear. k increases by at most 1 per step of i, and every fallback strictly decreases it. It can’t decrease more in total than it increased, so all the inner while loops together run at most m times. The same amortized argument as the sliding window.

Variations you’ll meet

Section titled “Variations you’ll meet”
  • Counting or listing all matches (including overlapping ones).
  • Period and repetition: is s a power of a shorter string? Smallest rotation? s is a rotation of t iff s occurs in t + t (and lengths match).
  • Borders of every prefix: walk π[n−1], π[π[n−1]−1], … to list all borders.
  • Automaton form: precompute next[state][char] from π to process each text character in O(1) without fallbacks (useful for DP over strings).
  • Multiple patterns: Aho-Corasick builds failure links on a trie, exactly like π on a single pattern.
  • Manacher’s algorithm: a Z-box-style trick for all palindromic substrings in O(n).
  • Suffix arrays / automata: for “longest repeated substring”, “number of distinct substrings” and similar whole-string questions.

Pitfalls

Section titled “Pitfalls”
  • Off-by-one in π. π[i] is a length, so the fallback is π[k−1], not π[k].
  • Proper border. π[i] must be shorter than i + 1; otherwise every string is its own border and the search never advances.
  • Forgetting overlapping matches. After a full match, fall back to π[m−1], don’t reset to 0.
  • Separator collision in p + '#' + t: pick a character that can’t appear in either string, or handle the boundary explicitly.
  • Empty pattern. Decide what to return (every position? nothing?) before coding.
  • Unicode. JS strings index UTF-16 code units, C# char too; Python indexes code points. Characters outside the BMP (emoji) are two units in JS/C#. Usually irrelevant in interviews, but say it if the input is “any text”.

In the interview

Section titled “In the interview”
  • Start with the naive O(n·m) approach and give the input that makes it slow (aaaa…ab).
  • Explain the key insight in one sentence: “After a mismatch, the part I already matched is a prefix of the pattern, so the shift depends only on the pattern. I precompute it.”
  • Write the prefix function slowly and test it on aabaaab by hand.
  • State the amortized argument for linear time.
  • Expect: “find all occurrences, overlapping”, “many patterns” (Aho-Corasick or a trie), “now use hashing” (Rabin-Karp), “what does your language’s indexOf do?”.

Check yourself

Section titled “Check yourself”
Check yourself
pick one
What is the prefix function of 'abab'?
Check yourself
pick one
A string of length 12 has π[11] = 8. Is it made of a repeated block, and if so how long?
Check yourself
pick one
Why does KMP never need to move the text pointer backwards?

Practice on your own

Section titled “Practice on your own”

Classic exercises (not gym questions):

  • Check whether a string is a rotation of another in O(n).
  • Shortest palindrome formed by adding characters only at the front (prefix function on s + '#' + reverse(s)).
  • Count how many times each prefix of s occurs in s.
  • Given s, find the smallest k such that s is a prefix of some repetition of s[:k].
  • Compress a string by finding the shortest block that repeats to form it.

Go deeper

Section titled “Go deeper”
Section titled “Related”
Rolling hash (Rabin-Karp)Matching and substring equality by hashing.
TriesMany patterns or prefixes at once.
String manipulationBuilding, slicing and comparing strings efficiently.
Sliding windowThe same amortized 'pointer never goes back' argument.