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.

flowchart TD
    Q{"What are you searching for<br/>identify the problem type"} --> A["Every occurrence of one pattern<br/>KMP pattern matching"]
    Q --> B["Repeated comparison of equal-length fragments<br/>rolling hash"]
    Q --> C["Prefix queries over many words<br/>trie"]
    Q --> D["Contiguous range satisfying a condition<br/>sliding window"]

Each algorithm reuses information that brute force discards. It can reduce comparison cost, skip unnecessary comparisons, or store a shared prefix only once.

The limits of brute force

A simple substring search tries to match the complete pattern at every starting position in the text. There are $N$ starting positions and up to $M$ comparisons per position, giving a worst case of $O(NM)$. The worst case occurs when matches repeatedly fail at the last character. Searching for aaaab in aaaa...ab is an example.

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 repeated structure inside the pattern. It uses this information to avoid moving the text pointer backward after a mismatch. The pi array, also called the failure function, stores these results. For the pattern substring from index 0 to index i, pi[i] gives the longest matching prefix and suffix length.

When a mismatch occurs at pattern index j, the pi array provides the next position. The algorithm moves j to pi[j-1] and continues comparing. It does not need to examine the matching prefix 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 one direction, giving a total cost of $O(N+M)$. The final value in the pi array also identifies the minimum repeating unit of a pattern. This supports problems that ask for a string's period.

Rolling hashes

A rolling hash represents a substring as one integer, making comparison close to $O(1)$. Rabin-Karp uses this method for pattern search. It treats the string as a number in a fixed base. When the window moves, the algorithm removes the leading character and adds the trailing character to update the hash. This avoids recomputing the entire hash.

To avoid overflow as values grow, the algorithm uses the remainder modulo a large prime. The example uses base 131 and modulus $2^{61}-1$. The Mersenne prime $2^{61}-1$ is common in modular arithmetic. The prime 131 is also a common base choice 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 stores shared prefixes of multiple strings along one path. To insert a word, follow child nodes for each character and mark the final node. For a word of length $L$, insertion and search both cost $O(L)$. The cost depends on word length rather than the number of words in the dictionary.

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 checks whether the complete prefix path exists. The end marker distinguishes an exact dictionary word from a prefix. To detect prefix conflicts, check whether insertion passes through a node already marked as a word end. Also check whether children remain below the final node 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 algorithm records the last position of each character. When a duplicate appears, it moves the left pointer past that position.

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

Two pointers finds pairs in sorted data. A sliding window tracks a condition over a contiguous range. String problems frequently involve range conditions, so sliding windows appear more often.

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, first define what the search must find. KMP finds occurrences of one pattern in $O(N+M)$. Rolling hashes compare equal-length fragments in $O(1)$ on average. Tries answer prefix queries over many words in $O(L)$. Sliding windows handle conditions over contiguous ranges in $O(N)$.

These algorithms reduce comparison cost by reusing information that brute force discards. Common implementation checks cover KMP jumps, rolling hash collisions, trie memory, and input preprocessing.