String Algorithms for Coding Tests

Left as brute force, string problems easily become $O(NM)$. Here are the criteria for cutting them down to linear or near-linear with four patterns.

The algorithm for a string problem depends on what you are searching for. The target varies: the position of a single pattern, a dictionary sharing prefixes, repeated fragments, a contiguous range satisfying a condition. In every case, comparing with nested loops times out as soon as the input grows a little. Classifying the problem type first and then picking the matching algorithm is the order that matters.

Problem types and selection criteria

Stating the question you have to answer in one line almost determines the algorithm. The table below lists four common types, the recommended algorithm, and its complexity. $N$ is the text length, $M$ the pattern length, and $L$ the length of a single word.

The same classification as a flowchart makes the choice clearer. The only decision criterion is what you are searching for in the text.

The table and the flowchart point at the same thing: reduce the cost of one comparison, skip the comparison entirely, or store a shared prefix only once. All three salvage the information brute force throws away.

The limits of brute force

The simplest substring search tries to match the pattern to the end at every starting position in the text. There are $N$ starting positions and up to $M$ character comparisons each, so the worst case is $O(NM)$. Inputs that almost match and then diverge at the last character, such as searching for aaaab in aaaa...ab, produce that worst case.

The problem is that on a mismatch the text pointer moves back one position and the pattern restarts from the beginning. The earlier part of the text has already been examined, and that information is discarded. KMP and rolling hashes eliminate this waste in different ways.

KMP pattern matching

KMP (Knuth-Morris-Pratt) precomputes the repeated structure inside the pattern so the text pointer never moves backward on a mismatch. The core is the pi array, also called the failure function. pi[i] holds the longest length at which a prefix and a suffix match within the substring of the pattern from index 0 to index i.

With the pi array, a mismatch at index j in the pattern jumps j to pi[j-1] and continues comparing, because the prefix that already matched does not need to be examined again.

def prefix_function(p):
    pi = [0] * len(p)
    j = 0
    for i in range(1, len(p)):
        while j > 0 and p[i] != p[j]:
            j = pi[j - 1]
        if p[i] == p[j]:
            j += 1
            pi[i] = j
    return pi

prefix_function("ababa") returns [0, 0, 1, 2, 3]. That array is used directly in the text search. The text pointer i never moves backward, and only the pattern pointer j jumps along pi.

def kmp_search(text, pat):
    pi = prefix_function(pat)
    res = []
    j = 0
    for i in range(len(text)):
        while j > 0 and text[i] != pat[j]:
            j = pi[j - 1]
        if text[i] == pat[j]:
            j += 1
            if j == len(pat):
                res.append(i - j + 1)
                j = pi[j - 1]
    return res

kmp_search("ababababa", "aba") returns [0, 2, 4, 6]. The text and pattern pointers each move in only one direction, so the whole thing is $O(N+M)$. The last value of the pi array is also used to find the minimum repeating unit of a pattern, so it applies directly to problems asking about the period of a string.

Rolling hashes

A rolling hash turns a substring into a single integer, making comparison close to $O(1)$. Applying this to pattern search gives the Rabin-Karp algorithm. It treats the string as a number in a fixed base and, when the window shifts by one, updates the hash by removing the leading character and adding the trailing one. Not recomputing the whole thing every time is the key.

Values overflow as they grow, so the remainder modulo a large prime is used. The example below sets the base to 131 and the modulus to $2^{61}-1$. $2^{61}-1$ is a Mersenne prime commonly used for modular arithmetic, and 131 is a prime frequently chosen as a base to reduce collisions.

def rabin_karp(text, pat, base=131, mod=(1 << 61) - 1):
    n, m = len(text), len(pat)
    if m > n:
        return []
    high = pow(base, m - 1, mod)
    ph = th = 0
    for i in range(m):
        ph = (ph * base + ord(pat[i])) % mod
        th = (th * base + ord(text[i])) % mod
    res = []
    for i in range(n - m + 1):
        if ph == th and text[i:i + m] == pat:
            res.append(i)
        if i < n - m:
            th = ((th - ord(text[i]) * high) * base + ord(text[i + m])) % mod
    return res

rabin_karp("ababababa", "aba") also returns [0, 2, 4, 6]. Note that equal hashes do not mean equal strings. Different strings can collide on the same hash, so the code above compares the actual strings once more when ph == th. To lower the collision probability further, use double hashing, computing the hash twice with different base and mod pairs.

Tries

A trie is a tree that gathers the common prefixes of multiple strings into a single path. Inserting a word walks down through child nodes character by character and marks the node where the word ends. If a word has length $L$, both insert and search are $O(L)$, proportional only to the length of one word and independent of how many words the dictionary holds.

class TrieNode:
    def __init__(self):
        self.child = {}
        self.end = False
 
class Trie:
    def __init__(self):
        self.root = TrieNode()
 
    def insert(self, word):
        cur = self.root
        for ch in word:
            if ch not in cur.child:
                cur.child[ch] = TrieNode()
            cur = cur.child[ch]
        cur.end = True
 
    def starts_with(self, prefix):
        cur = self.root
        for ch in prefix:
            if ch not in cur.child:
                return False
            cur = cur.child[ch]
        return True

starts_with only checks whether the prefix path exists all the way through. The end marker is what distinguishes whether exactly that word is in the dictionary. For problems that detect prefix conflicts, check whether inserting a word passes through a node already marked as an end, or whether children remain below it after insertion.

That said, with a large alphabet and many words the node count grows fast and memory becomes a burden. So if the question is only membership, a hash set is often lighter.

Sliding windows and two pointers

The sliding window pattern handles contiguous ranges in $O(N)$ by moving only the two endpoints. The right pointer widens the window, and the left pointer shrinks it when the condition is violated. In strings, the classic case is finding the longest substring without repeated characters.

def longest_unique(s):
    last = {}
    left = 0
    best = 0
    for right, ch in enumerate(s):
        if ch in last and last[ch] >= left:
            left = last[ch] + 1
        last[ch] = right
        best = max(best, right - left + 1)
    return best

longest_unique("abcabcbb") returns 3, and longest_unique("pwwkew") also returns 3. The last position of each character is remembered, and on a duplicate the left pointer is pulled to just past that position.

Two pointers looks similar but applies under different conditions. The table below draws the distinction.

In short, two pointers is for finding pairs in sorted data, and sliding windows for tracking a condition over a contiguous range. String problems involve range conditions often, so sliding windows come up more.

Common mistakes

All four algorithms have spots where implementation errors concentrate. The following are where points are most often lost under exam conditions.

• In KMP, decrementing j by 1 instead of jumping along pi in a while loop on a mismatch degrades to $O(NM)$.
• In a rolling hash, omitting the modulus causes overflow, and skipping the collision check produces wrong answers.
• Failing to account for trie node count explosion causes a memory limit exceeded.
• Preprocessing rules such as case, whitespace, and Unicode get missed in the input.

The last item looks unrelated to the algorithm but is a frequent cause of failure at judging time. Writing down the input character set and normalization rules before writing the solution is a safe habit. For practice, BOJ 1786 (Find) exercises KMP and BOJ 5052 (Phone List) lets you see trie prefix conflicts directly.

Summary

For string problems, defining in one line what you are searching for in the text almost determines the algorithm. Occurrences of a single pattern go to KMP at $O(N+M)$, and repeated comparison of equal-length fragments goes to a rolling hash at $O(1)$ comparison on average. Prefix queries over many words are solved with a trie at $O(L)$, and contiguous range conditions with a sliding window at $O(N)$.

All four share the property of reusing the information brute force throws away in order to reduce comparison cost. In implementation, checking four things, the jump in KMP, collision verification in a rolling hash, memory in a trie, and input preprocessing, avoids the common point deductions.