Algorithm Design Paradigms

String Matching

Finding a pattern inside a text faster than the naive O(nm) character-by-character scan — by reusing information the pattern itself reveals (KMP), hashing substrings (Rabin-Karp), or indexing the text (Tries).

Naive matching re-checks characters after every mismatch — O(nm) worst case, quadratic on adversarial or repetitive input
Knuth-Morris-Pratt (KMP) precomputes a "failure function" over the pattern so a mismatch never re-examines text already matched — O(n + m)
Rabin-Karp hashes substrings of the text using a rolling hash and compares hashes instead of characters — expected O(n + m), with O(nm) if hash collisions are adversarial
A Tries or suffix-structure approach amortizes cost across many pattern searches against the same text — build once, query many patterns fast
Choice depends on the workload: one pattern vs. many patterns vs. many texts changes which algorithm actually wins

String matching approaches
Algorithm	Time	Best for
Naive scan	O(nm) worst case	short pattern, one-off search, simplicity
KMP	O(n + m), always	guaranteed linear time regardless of input
Rabin-Karp	O(n + m) expected	searching for multiple patterns of the same length at once (hash each, compare)
Trie / Aho-Corasick over patterns	O(n + m + z) for z matches	many patterns searched against the same text repeatedly

KMP failure function — the key idea

int[] buildFailureFunction(String pattern) {
    int[] fail = new int[pattern.length()];
    int len = 0;                       // length of the current matching prefix
    for (int i = 1; i < pattern.length(); i++) {
        while (len > 0 && pattern.charAt(i) != pattern.charAt(len)) {
            len = fail[len - 1];        // fall back to a shorter prefix, don't rescan text
        }
        if (pattern.charAt(i) == pattern.charAt(len)) len++;
        fail[i] = len;
    }
    return fail;
}

fail[i] = length of the longest proper prefix of pattern[0..i] that is also a suffix of it — this is what lets matching skip ahead on a mismatch

The insight behind KMP: when a mismatch occurs after matching k characters of the pattern, the naive algorithm slides the pattern one position and starts over from scratch — but the k characters already matched contain information. If the pattern has an internal prefix that repeats, matching can resume from partway through the pattern instead of from its start, without ever re-reading a text character it already looked at. That guarantee — text characters are examined at most twice total — is what makes KMP O(n + m) instead of O(nm).