String Matching · Algorithms (DAA)

Given a text T of length n and a pattern P of length m, find every position where P occurs in T. This runs every time you press Ctrl+F, search DNA databases, or filter spam.

Naive algorithm

Try every alignment of P against T and compare character by character.

C++

#include <iostream>
#include <string>
using namespace std;

int main() {
    string T = "AABAACAADAABAABA", P = "AABA";
    int comparisons = 0;
    for (size_t s = 0; s + P.size() <= T.size(); s++) {
        size_t j = 0;
        while (j < P.size()) { comparisons++; if (T[s + j] != P[j]) break; j++; }
        if (j == P.size()) cout << "match at " << s << endl;
    }
    cout << "comparisons: " << comparisons << endl;
    return 0;
}

Output

match at 0
match at 9
match at 12
comparisons: 30

Try it Yourself

Worst case O((n − m + 1) · m), e.g. T = "aaaa…a", P = "aaab".

Rabin–Karp

Compare hash values first, and only compare characters when the hashes match. The trick is a rolling hash: the hash of the next window is computed from the previous one in O(1) by removing the leading character and adding the trailing one.

C++

#include <iostream>
#include <string>
using namespace std;

int main() {
    string T = "31415926535897932384626", P = "26";
    const long long base = 10, mod = 13;
    int n = T.size(), m = P.size();
    long long h = 1;                                   // base^(m-1) % mod
    for (int i = 0; i < m - 1; i++) h = h * base % mod;
    long long hp = 0, ht = 0;
    for (int i = 0; i < m; i++) { hp = (hp * base + (P[i] - '0')) % mod; ht = (ht * base + (T[i] - '0')) % mod; }
    int spurious = 0;
    for (int s = 0; s + m <= n; s++) {
        if (hp == ht) {
            if (T.compare(s, m, P) == 0) cout << "match at " << s << endl;
            else spurious++;                                 // hash collision
        }
        if (s + m < n) ht = ((ht - (T[s] - '0') * h % mod + mod) * base + (T[s + m] - '0')) % mod;   // roll
    }
    cout << "spurious hits: " << spurious << endl;
    return 0;
}

Output

match at 6
match at 21
spurious hits: 1

Try it Yourself

Expected time O(n + m); worst case O(nm) if many hashes collide (a "spurious hit"). Rabin–Karp shines when searching for many patterns at once.

Knuth–Morris–Pratt (KMP)

When a mismatch happens, the naive algorithm slides the pattern by one and re-checks characters it has already seen. KMP never moves backwards in the text. It precomputes the prefix function π (also called the LPS array): π[q] = the length of the longest proper prefix of P[0..q] that is also a suffix of it. On a mismatch, it shifts the pattern so that this already-matched prefix lines up.

For P = "ABABCABAB": π = [0, 0, 1, 2, 0, 1, 2, 3, 4].

C++

#include <iostream>
#include <string>
#include <vector>
using namespace std;

vector<int> prefixFunction(const string &P) {
    vector<int> pi(P.size(), 0);
    for (size_t q = 1, k = 0; q < P.size(); q++) {
        while (k > 0 && P[k] != P[q]) k = pi[k - 1];     // fall back to a shorter border
        if (P[k] == P[q]) k++;
        pi[q] = k;
    }
    return pi;
}

int main() {
    string T = "ABABDABACDABABCABABABABCABAB", P = "ABABCABAB";
    vector<int> pi = prefixFunction(P);
    cout << "pi:";
    for (int x : pi) cout << " " << x;
    cout << endl;
    for (size_t i = 0, q = 0; i < T.size(); i++) {
        while (q > 0 && P[q] != T[i]) q = pi[q - 1];
        if (P[q] == T[i]) q++;
        if (q == P.size()) { cout << "match at " << i - P.size() + 1 << endl; q = pi[q - 1]; }
    }
    return 0;
}

Output

pi: 0 0 1 2 0 1 2 3 4
match at 10
match at 19

Try it Yourself

Preprocessing O(m) + matching O(n) = O(n + m) in the worst case.

Algorithm	Preprocessing	Matching (worst)	Idea
Naive	none	O((n − m + 1)m)	try every shift
Rabin–Karp	O(m)	O((n − m + 1)m), expected O(n + m)	rolling hash
KMP	O(m)	O(n)	prefix function, never backtrack in T
Finite automaton	O(m·	Σ	)

Test yourself

4 questions · pick an answer to check it instantly

1
What is the worst-case time of the naive matcher?
2
What is a spurious hit in Rabin–Karp?
3
What is the prefix function of "AAAA"?
4
Why is KMP O(n + m) in the worst case?

#Naive algorithm

#Rabin–Karp

#Knuth–Morris–Pratt (KMP)

Test yourself

Naive algorithm

Rabin–Karp

Knuth–Morris–Pratt (KMP)