String Algorithms

When to use string search algorithms

Use a string search algorithm when you need to:

• Find every occurrence of a pattern in a long text, in time that grows with the text length (O(n + m)), not with text length times pattern length.
• Search the same pattern in a huge stream, such as a log file or a network packet, where re-reading characters is expensive.
• Compare many substrings quickly by their hashes (plagiarism checks, duplicate detection, finding repeated DNA sequences).
• Measure how a string matches its own start (the Z-algorithm), which is the base of many "prefix" problems.

Use something else when:

• You search for a single word once in a short string: use your language's built-in find or indexOf. It is fast and well tested.
• You search for many different patterns at once (a dictionary of banned words): use a trie with failure links (Aho-Corasick), not one search per pattern.
• You need fuzzy matches (typos, wildcards): use edit distance, regular expressions or a search engine.
• You search a fixed text with many different patterns: build a suffix array or suffix automaton once, then answer each query fast.

Do not write your own search in production. Use String.indexOf, str.find, strings.Index or the like (see the real-world section). Writing KMP by hand is for learning and interviews.

How string search works

The obvious method, naive search, tries the pattern at every position of the text and compares character by character. When a comparison fails it forgets everything and starts again one position later. On text like aaaaaaaaaab with pattern aaaab it re-reads the same characters over and over: O(n × m) comparisons.

The three classic algorithms each remember something so they never repeat work:

KMP remembers how much of the pattern already matched, so the text pointer never moves backwards. Rabin-Karp compares a small number (a hash) instead of the characters. Z-algorithm measures, for every position, how long the text there matches the start of the pattern.

• KMP first builds a failure table from the pattern alone. For each prefix of the pattern, the table says the length of the longest part that is both a prefix and a suffix of it (a border). After a mismatch, the pattern slides forward by that border instead of starting again.
• Rabin-Karp treats a window of text as a number (a rolling hash). Moving the window one place right updates the hash in O(1): subtract the leaving character, shift, add the new one. Only when two hashes are equal does it compare characters, because different strings can share a hash (a collision).
• Z-algorithm builds an array where Z[i] is the length of the longest match between the string starting at i and the string's own start. Join pattern + "#" + text, and any Z[i] equal to the pattern length marks a match.

Try it

Pick an algorithm and an input, then step through. Watch the comparisons counter.

Things to try:

• Run Naive on Repeating text (aaaaaaaaaab, pattern aaaab). It makes 35 comparisons, because it re-reads the as at every shift. Switch to KMP: 17 comparisons for the same answer, and never more than 2 per text character.
• Run Rabin-Karp on Ordinary text. Most windows are skipped after a single hash comparison, with no character comparisons at all.
• Run Naive, then KMP, on Ordinary text (the quick brown fox, pattern brown). Both make 19 comparisons. KMP is not magic: it only wins when the text has partial matches to reuse. Ordinary text has almost none, so naive is already fast there.
• On the same Ordinary text, step through Rabin-Karp and watch for the one false alarm. With the toy modulus 101, one window has the same hash as brown but different characters, so the character check is needed and rejects it. Do not expect "no false alarms".
• Run KMP on Pattern is not in the text, then look at the failure table row: the table, not the text, decides how far to fall back.

String search operations: build the table, search and verify

Naive. For each shift s, compare text[s + j] with pattern[j] for j = 0, 1, ... until a mismatch or a full match.

KMP. There are two phases:

1. Build the failure table f for the pattern in O(m). f[i] is the length of the longest proper prefix of pattern[0..i] that is also its suffix.
2. Scan the text once. Keep j, the number of pattern characters matched. If text[i] equals pattern[j], add one to j. On a mismatch, set j = f[j - 1] and compare again (without moving i). When j equals the pattern length, record a match and set j = f[j - 1] to keep going.

Rabin-Karp. Compute the pattern's hash and the hash of the first window. Slide the window, updating the hash in O(1). When the hashes are equal, compare the characters to rule out a collision.

Rabin-Karp in Python. This is a short, runnable version. It uses the same base 256 and modulus 101 as the simulation.

def rabin_karp(text, pattern, base=256, mod=101):
    n, m = len(text), len(pattern)
    if m == 0 or m > n:
        return []
    high = pow(base, m - 1, mod)  # weight of the leaving character
    hp = hw = 0
    for i in range(m):
        hp = (hp * base + ord(pattern[i])) % mod
        hw = (hw * base + ord(text[i])) % mod
    found = []
    for s in range(n - m + 1):
        if hw == hp and text[s:s + m] == pattern:  # verify: equal hashes can collide
            found.append(s)
        if s + m < n:
            hw = ((hw - ord(text[s]) * high) * base + ord(text[s + m])) % mod
    return found

The modulus 101 is a toy value, chosen so that collisions are easy to see in the simulation. Real code uses a very large prime (or two hashes), which makes false alarms rare. Python's % always gives a non-negative result, but in Java, C++ or JavaScript the subtraction can go negative, so add mod and take % again.

Z-algorithm. Keep a window [l, r) of the rightmost match found so far. For a new position i inside it, reuse the earlier answer Z[i - l] (capped at r - i) and extend only if needed.

Z-algorithm in Python. The same window idea as above, in code.

def z_array(s):
    n = len(s)
    z = [0] * n
    z[0] = n
    l = r = 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

def z_search(text, pattern):
    z = z_array(pattern + "#" + text)
    m = len(pattern)
    return [i - m - 1 for i in range(m + 1, len(z)) if z[i] == m]

z_search("aaaaaaaaaab", "aaaab") returns [6]. Use a separator such as # that never appears in the pattern or text, otherwise a match could run across the join.

Why the Z-algorithm is linear. The right edge r of the window only ever moves right. Each character comparison either extends r (at most n times in total) or ends the while loop for that i (once per i). So the total work is O(n) for the joined string of length n + m + 1.

KMP never moves its text pointer backwards, so the text can be read from a stream. This is the interview fact. Each character causes at most one forward step and some fall-backs, and the fall-backs can never exceed the forward steps, so the total is O(n).

Dry run: failure table and KMP

Building the failure table for aabaaab. Keep k, the length of the border found so far. For each i from 1, compare p[i] with p[k]. On a mismatch, fall back with k = f[k - 1] until they match or k is 0.

The table is 0 1 0 1 2 2 3. Row 5 is the important one: the fall-back reuses the table instead of starting again.

KMP on text aaaaaaaaaab, pattern aaaab. The failure table is 0 1 2 3 0. Count one comparison each time text[i] is compared with pattern[j].

1. i = 0 to 3: each a matches, so j grows to 4. That is 4 comparisons.
2. i = 4: a against pattern[4] (b) fails (1 comparison). Fall back to j = f[3] = 3. Compare again: a matches pattern[3], j is 4 again (1 comparison). That is 2 comparisons.
3. i = 5 to 9 repeat step 2: 2 comparisons each, so 10 more. Steps 2 and 3 together cover i = 4 to 9: 12 comparisons.
4. i = 10: b matches pattern[4], j is 5, the pattern length. That is 1 comparison, and a match is recorded at 10 - 5 + 1 = 6.

Total: 4 + 12 + 1 = 17 comparisons, with the match at index 6. Naive makes 35. The text pointer i never moved back.

How to recognise the pattern

Think of KMP, Z or a rolling hash when the problem says:

• "Find all occurrences of a pattern" in a long text or stream: KMP, Z or Rabin-Karp.
• "Smallest period" or "is the string made of a repeated block": the failure table. If n - f[n - 1] divides n (and f[n - 1] is not 0), that value is the period length.
• "Shortest palindrome by adding characters at the front": the failure table of s + "#" + reverse(s).
• "Longest prefix that is also a suffix" (a border): the last failure value.
• "Is one string a rotation of another": search for b inside a + a (same length required).
• "Repeated substrings of a fixed length" (for example DNA sequences): a rolling hash with a set, then verify.
• "How much does each suffix match the start of the string": the Z-array.
• "Many patterns at once": think Aho-Corasick or a trie, not repeated searches.

Edge cases and common mistakes

• Empty pattern. Code that reads pattern[0] fails. Decide the rule first. Most libraries (and the usual strStr convention) treat an empty pattern as matching at index 0. Return early before building any table.
• Pattern longer than the text. There are no windows. Return no matches before computing a hash or indexing the text.
• Overlapping matches. Searching aaa in aaaaa has three matches, at 0, 1 and 2. After a full match, KMP sets j = f[j - 1], not 0, so overlaps are found. Resetting j to 0 silently misses them.
• Off-by-one match index. When j reaches the pattern length at text index i, the match starts at i - m + 1, not i - m. In the Z-array on the joined string, subtract m + 1 (the pattern and the separator).
• Skipping the Rabin-Karp check. Equal hashes do not prove equal strings. Without the character comparison the answer is wrong whenever there is a collision.
• Negative modulus. In languages where % can return a negative number, the rolling update can go negative. Add the modulus and take % again.
• Non-ASCII text. Indexing a string by position may mean bytes, UTF-16 units or code points, depending on the language. A match index in one unit is not the same in another. Decide the unit, and be careful with characters outside the basic range, since they may take more than one unit.
• Separator inside the data. In the Z and palindrome tricks, the separator must not appear in the input.

String search time complexity

Here n is the text length and m the pattern length. Rabin-Karp's worst case happens when many windows share the pattern's hash, which a good modulus and base make very unlikely. Its great strength is searching for many patterns of the same length at once with one rolling hash.

String search vs other approaches

Here n is the text length and m the pattern length. These algorithms win when one pattern is searched with a guaranteed worst case, or when hashing helps. They never beat a suffix structure when the text is fixed and the patterns change.

How to explain string search in an interview

• Start with the naive approach and its O(n × m) cost, and show the input that makes it slow (aaaa...ab). That shows why remembering matters.
• For KMP, say the idea first: "never move the text pointer back; the failure table says how far to fall back in the pattern." Then give O(n + m) time and O(m) space.
• For Rabin-Karp, say that equal hashes must be verified, and that a rolling hash updates in O(1). Mention that it extends naturally to 2D patterns and to many patterns.
• Name the practical answer: "In production I would call the library's find; I would reach for KMP when I need a guaranteed worst case or must work on a stream."