v. Other Matching Algorithms

Matching beyond KMP / Z / Aho–Corasick: Boyer–Moore (sublinear in practice), bit-parallel automata (shift-and / shift-or, Bitap with $k$ errors, Myers’ bit-vector edit distance), bitset matching under updates, wildcard matching by FFT, glob patterns, and the containment relation of a pattern set. Rabin–Karp is in String Hashing.

Situation	Best tool	Cost
exact, one pattern, worst-case guarantee	KMP / Z (Prefix Function and Z)	$O(n+m)$
exact, long pattern, large alphabet, practice	Boyer–Moore / Horspool	sublinear on average, $O(nm)$ worst (bad-character only)
exact, pattern $\le 64$, huge text	shift-or / shift-and	$O(n)$, two instructions per character
$\le k$ errors (Levenshtein), small $k$	Bitap (Wu–Manber)	$O(kn\lceil m/w\rceil )$
edit distance / approximate search, any $k$	Myers’ bit-vector	$O(n\lceil m/w\rceil )$
many patterns	Aho–Corasick	$O(n+m+\text{occ})$
text with point updates, occurrences in ranges (CF 914F)	bitset shift-and	$O(|p|n/64)$ per query
wildcards ? on either side	three FFT correlations of $\sum p_j{t}_{i+j}(p_j-t_{i+j}{)}^2$	$O(n\log n)$
* = any substring (glob)	split at stars, match pieces greedily with KMP; or DP	$O(n+m)$ / $O(nm)$
which patterns are substrings of which (CF 590E)	Aho–Corasick + bitset closure	$O(L\sigma +k^3/64)$

vector<int> boyerMoore(const string& t, const string& p) { // bad character + good suffix, all occurrences
    int n = sz(t), m = sz(p); vector<int> res; if (m == 0 || m > n) return res;
    vector<int> last(256, -1); for (int i = 0; i < m; i++) last[(unsigned char)p[i]] = i;
    vector<int> suff(m), good(m + 1, m);                    // suff[i]: longest common suffix of p and p[0..i]
    suff[m - 1] = m;
    for (int i = m - 2; i >= 0; i--) { int k = 0; while (k <= i && p[i - k] == p[m - 1 - k]) k++; suff[i] = k; }   // O(m^2) worst, fine for contests
    for (int i = m - 1, j = 0; i >= 0; i--) if (suff[i] == i + 1) for (; j < m - 1 - i; j++) if (good[j] == m) good[j] = m - 1 - i;   // case 2: prefix = suffix
    for (int i = 0; i <= m - 2; i++) good[m - 1 - suff[i]] = m - 1 - i;   // case 1: reoccurrence of the matched suffix
    for (int s = 0; s <= n - m;) {
        int j = m - 1; while (j >= 0 && p[j] == t[s + j]) j--;
        if (j < 0) { res.push_back(s); s += good[0]; }
        else s += max(good[j], j - last[(unsigned char)t[s + j]]);
    }
    return res;
}
vector<int> horspool(const string& t, const string& p) {   // bad character of the window's last symbol only
    int n = sz(t), m = sz(p); vector<int> res; if (m == 0 || m > n) return res;
    vector<int> shift(256, m); for (int i = 0; i + 1 < m; i++) shift[(unsigned char)p[i]] = m - 1 - i;
    for (int s = 0; s <= n - m; s += shift[(unsigned char)t[s + m - 1]]) if (t.compare(s, m, p) == 0) res.push_back(s);
    return res;
}
vector<int> shiftAnd(const string& t, const string& p) {   // |p| <= 64
    int m = sz(p); vector<int> res; if (m == 0 || m > 64) return res;
    array<ull, 256> B{}; for (int j = 0; j < m; j++) B[(unsigned char)p[j]] |= 1ULL << j;
    ull D = 0, top = 1ULL << (m - 1);
    for (int i = 0; i < sz(t); i++) { D = ((D << 1) | 1) & B[(unsigned char)t[i]]; if (D & top) res.push_back(i - m + 1); }
    return res;
}
vector<int> shiftOr(const string& t, const string& p) {    // complemented: no "| 1" needed
    int m = sz(p); vector<int> res; if (m == 0 || m > 64) return res;
    array<ull, 256> B; B.fill(~0ULL); for (int j = 0; j < m; j++) B[(unsigned char)p[j]] &= ~(1ULL << j);
    ull D = ~0ULL, top = 1ULL << (m - 1);
    for (int i = 0; i < sz(t); i++) { D = (D << 1) | B[(unsigned char)t[i]]; if (!(D & top)) res.push_back(i - m + 1); }
    return res;
}
vector<int> bitapApprox(const string& t, const string& p, int k) {   // end positions with a match of <= k edits, |p| <= 63
    int m = sz(p); vector<int> res; if (m == 0 || m > 63) return res;
    array<ull, 256> B{}; for (int j = 0; j < m; j++) B[(unsigned char)p[j]] |= 1ULL << j;
    vector<ull> R(k + 1); for (int d = 0; d <= k; d++) R[d] = (1ULL << d) - 1;   // d leading pattern chars may be deleted
    ull top = 1ULL << (m - 1);
    for (int i = 0; i < sz(t); i++) {
        ull old = R[0], c = B[(unsigned char)t[i]];
        R[0] = ((R[0] << 1) | 1) & c;
        for (int d = 1; d <= k; d++) {
            ull tmp = R[d];
            R[d] = (((R[d] << 1) | 1) & c) | old | ((old | R[d - 1]) << 1) | 1;   // match | insertion | substitution, deletion
            old = tmp;
        }
        if (R[k] & top) res.push_back(i);
    }
    return res;
}
int myersDistance(const string& p, const string& t, bool search = false) {   // |p| <= 64; global edit distance, or min over substrings of t if search
    int m = sz(p); if (m == 0) return search ? 0 : sz(t);
    array<ull, 256> Peq{}; for (int j = 0; j < m; j++) Peq[(unsigned char)p[j]] |= 1ULL << j;
    ull Pv = ~0ULL, Mv = 0, top = 1ULL << (m - 1); int score = m, best = m;
    for (char ch : t) {
        ull Eq = Peq[(unsigned char)ch], Xv = Eq | Mv, Xh = (((Eq & Pv) + Pv) ^ Pv) | Eq;
        ull Ph = Mv | ~(Xh | Pv), Mh = Pv & Xh;
        if (Ph & top) score++; else if (Mh & top) score--;
        Ph = (Ph << 1) | (search ? 0 : 1); Mh <<= 1;       // row 0: +1 per column (global) or 0 (search)
        Pv = Mh | ~(Xv | Ph); Mv = Ph & Xv;
        best = min(best, score);
    }
    return search ? best : score;
}

Proof: Boyer–Moore shifts and the bit-parallel automata

Boyer–Moore. Comparing right to left, a mismatch at $p_j\ne t_{s+j}$ after matching the suffix $u=p[j+\mathrm{1..}m)$ allows a shift to the next alignment consistent with what was read: the bad-character shift aligns $t_{s+j}$ with its last occurrence in $p$ (or moves past it), and the good-suffix shift aligns $u$ with its previous occurrence in $p$ not preceded by $p_j$ (case 1, from suff) or, failing that, aligns the longest prefix of $p$ that is a suffix of $u$ (case 2). Both are the minimum shifts not contradicting the information read, so taking the maximum skips no occurrence; after a full match the good-suffix shift of the whole pattern is the smallest period. Horspool uses only the bad character of the window’s last symbol (safe for the same reason). Shift-and: state bit $j$ means ”$p[\mathrm{0..}j]$ is a suffix of the text read”; it becomes true iff bit $j-1$ was (or $j=0$) and the new character equals $p_j$: $D\leftarrow ((D\ll 1)\mid 1)\&B[c]$. Shift-or stores the complement, and the shift brings in the 0 that the | 1 provided. Bitap with errors: $R_d$ bit $j$ means $p[\mathrm{0..}j]$ matches a suffix of the text with $\le d$ edits; the recurrence takes the union of match, substitution ($R_{d-1}$ shifted), insertion of a text character ($R_{d-1}$ unshifted) and deletion of a pattern character ($R_d$ new shifted), the standard Wu–Manber derivation; initialising $R_d$ with the low $d$ bits accounts for deleting a prefix of $p$. Myers: the vertical and horizontal differences of the edit DP column are in $\{-1,0,1\}$ and are encoded by the bit vectors $P_v,M_v,P_h,M_h$; the carry in $(Eq\&P_v)+P_v$ propagates exactly the runs where the minimum comes from the diagonal (Myers 1999, Hyyrö’s formulation), and the score tracks the bottom row. The row-0 boundary is $+1$ per column for the global distance and $0$ for approximate search. All four were checked against brute force and the $O(nm)$ DP on random strings.

Bitset matching with updates

occ = AND_j (mask[p_j] >> j): bit $i$ survives iff $s_{i+j}=p_j$ for all $j$. A point update flips two bits; a query costs $|p|\cdot n/64$, fast enough for $n,\sum |p|\approx 10^5$ (CF 914F). Without updates use KMP / Z; with wildcards, below.

template <int N> struct BitsetMatcher {                     // lowercase text of length n <= N
    int n; string s; vector<bitset<N>> mask;
    BitsetMatcher(const string& str) : n(sz(str)), s(str), mask(26) { for (int i = 0; i < n; i++) mask[s[i] - 'a'][i] = 1; }
    void set(int i, char c) { mask[s[i] - 'a'][i] = 0; s[i] = c; mask[c - 'a'][i] = 1; }
    bitset<N> occurrences(const string& p) const { bitset<N> occ; occ.set(); for (int j = 0; j < sz(p); j++) occ &= mask[p[j] - 'a'] >> j; return occ; }
    int count(int l, int r, const string& p) const {      // occurrences fully inside s[l, r)
        int m = sz(p); if (r - l < m) return 0;
        bitset<N> occ = occurrences(p); int hi = r - m + 1; // starts in [l, hi)
        return ((occ >> l) << (N - (hi - l))).count();
    }
};

Wildcard matching by FFT

Give symbols random non-zero values $x$ and the wildcard 0. Position $i$ scores ${\sum }_j{p}_j{t}_{i+j}(p_j-t_{i+j}{)}^2=\sum p^{3}t-2p^2{t}^2+p{t}^3$: three correlations. The score is a non-zero degree-4 polynomial in the random values when some non-wildcard pair mismatches, so a false match needs a zero modulo both primes, probability $\le 16/(998244353\cdot 469762049)$ per position. Works for any symbol type; counting mismatches per alignment needs one convolution per symbol instead. Uses ntt from NTT.

template <int P, class T> vector<Mint<P>> wildcardScores(const T& text, const T& pat, typename T::value_type wild, mt19937_64& rng) {
    using Z = Mint<P>; int n = sz(text), m = sz(pat);
    map<typename T::value_type, Z> code;
    auto value = [&](typename T::value_type x) { if (x == wild) return Z(0); auto it = code.find(x); if (it == code.end()) it = code.emplace(x, Z(ll(rng() % (P - 1)) + 1)).first; return it->second; };
    int N = 1; while (N < n) N *= 2;                        // cyclic wrap only lands on indices < m - 1, unused
    vector<Z> a1(N), a2(N), a3(N), b1(N), b2(N), b3(N);
    for (int j = 0; j < m; j++) { Z x = value(pat[m - 1 - j]); a1[j] = x; a2[j] = x * x; a3[j] = x * x * x; }   // reversed pattern
    for (int i = 0; i < n; i++) { Z y = value(text[i]); b1[i] = y; b2[i] = y * y; b3[i] = y * y * y; }
    for (vector<Z>* v : {&a1, &a2, &a3, &b1, &b2, &b3}) ntt(*v);
    vector<Z> c(N); for (int k = 0; k < N; k++) c[k] = a3[k] * b1[k] - Z(2) * a2[k] * b2[k] + a1[k] * b3[k];
    ntt(c, true);
    return vector<Z>(c.begin() + m - 1, c.begin() + n);     // c[i + m - 1] scores text[i, i + m)
}
template <class T> vector<int> wildcardMatch(const T& text, const T& pat, typename T::value_type wild) {
    int n = sz(text), m = sz(pat); assert(m > 0); if (m > n) return {};
    mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
    auto s1 = wildcardScores<998244353>(text, pat, wild, rng); auto s2 = wildcardScores<469762049>(text, pat, wild, rng);
    vector<int> pos; for (int i = 0; i <= n - m; i++) if (s1[i] == Mint<998244353>(0) && s2[i] == Mint<469762049>(0)) pos.push_back(i);
    return pos;
}
bool globMatch(const string& t, const string& p) {          // '?' any char, '*' any substring; O(nm) DP
    int n = sz(t), m = sz(p); vector<char> dp(m + 1, 0), nd(m + 1); dp[0] = 1;
    for (int j = 1; j <= m; j++) dp[j] = dp[j - 1] && p[j - 1] == '*';
    for (int i = 1; i <= n; i++) {
        nd[0] = 0;
        for (int j = 1; j <= m; j++) nd[j] = p[j - 1] == '*' ? (nd[j - 1] || dp[j]) : (dp[j - 1] && (p[j - 1] == '?' || p[j - 1] == t[i - 1]));
        dp = nd;
    }
    return dp[m];
}

Proof: the wildcard score and glob DP

For an alignment the score is ${\sum }_j{p}_j{t}_j(p_j-t_j{)}^2$ with $p_j,t_j$ the random codes (0 for wildcards). Every term with a wildcard vanishes, and a term with two equal symbols vanishes; if some pair of distinct symbols is aligned, the score as a polynomial in the random codes contains the monomial $x_a{x}_b^3$ (or similar) with a non-zero coefficient, so it is a non-zero polynomial of degree 4 and by Schwartz–Zippel vanishes with probability $\le 4/(P-1)$ per prime; two independent primes multiply the probabilities. The correlation with the reversed pattern is a convolution, and coefficient $i+m-1$ collects exactly the pairs $(j,i+j)$; wrap-around of the cyclic product only reaches indices $<m-1$. Glob DP: dp[j] says $t[\mathrm{0..}i)$ matches $p[\mathrm{0..}j)$; a star either matches nothing (nd[j-1]) or absorbs $t_{i-1}$ and stays (dp[j]), any other symbol consumes one character. Verified against brute force (regex-style recursion, direct comparison with wildcards).

Pattern containment

For $k$ strings of total length $L$, compute “pattern $i$ occurs inside pattern $j$” for all pairs. Scanning pattern $j$ through the Aho–Corasick automaton, record at every position only the longest pattern ending there (nearest terminal on the suffix-link chain, excluding the whole of $p_j$ at its last position); every other contained pattern is a substring of a recorded one, so a transitive closure over $O(L)$ direct edges recovers the relation. Equal patterns contain each other. Typical next step: maximum antichain $=k-$ maximum matching in the comparability DAG (Dilworth, CF 590E Birthday).

vector<vector<char>> patternContainment(const vector<string>& pats) {   // in[i][j] = pats[i] is a substring of pats[j]
    int k = sz(pats); vector<array<int, 26>> go(1); go[0].fill(0);
    vector<int> link(1, 0), term(1, -1), outLink(1, -1), endNode(k);
    for (int i = 0; i < k; i++) {
        int v = 0;
        for (char ch : pats[i]) { int c = ch - 'a'; if (!go[v][c]) { go[v][c] = sz(go); go.emplace_back(); go.back().fill(0); link.push_back(0), term.push_back(-1), outLink.push_back(-1); } v = go[v][c]; }
        if (term[v] == -1) term[v] = i;
        endNode[i] = v;
    }
    vector<int> q; for (int c = 0; c < 26; c++) if (go[0][c]) q.push_back(go[0][c]);
    for (int i = 0; i < sz(q); i++) {
        int v = q[i]; outLink[v] = term[link[v]] != -1 ? link[v] : outLink[link[v]];   // nearest proper terminal suffix
        for (int c = 0; c < 26; c++) { int u = go[v][c]; if (u) link[u] = go[link[v]][c], q.push_back(u); else go[v][c] = go[link[v]][c]; }
    }
    int W = (k + 63) / 64; vector<vector<ull>> reach(k, vector<ull>(W, 0));   // reach[j] bit i: pats[i] inside pats[j]
    auto mark = [&](int j, int i) { reach[j][i >> 6] |= 1ULL << (i & 63); };
    for (int j = 0; j < k; j++) {
        int v = 0, len = sz(pats[j]);
        for (int p = 0; p < len; p++) {
            v = go[v][pats[j][p] - 'a'];
            int best = p + 1 == len ? outLink[v] : (term[v] != -1 ? v : outLink[v]);
            if (best != -1) mark(j, term[best]);
        }
        mark(j, j); mark(j, term[endNode[j]]);
    }
    for (int i = 0; i < k; i++) mark(term[endNode[i]], i);  // the representative of equal patterns contains every copy
    vector<int> order(k); iota(all(order), 0);
    stable_sort(all(order), [&](int a, int b) { return sz(pats[a]) < sz(pats[b]); });
    for (int j : order) for (int changed = 1; changed;) {   // closure; contained patterns are not longer
        changed = 0;
        for (int i = 0; i < k; i++) {
            if (i == j || !(reach[j][i >> 6] >> (i & 63) & 1)) continue;
            for (int w = 0; w < W; w++) { ull nw = reach[j][w] | reach[i][w]; if (nw != reach[j][w]) reach[j][w] = nw, changed = 1; }
        }
    }
    vector<vector<char>> in(k, vector<char>(k, 0));
    for (int j = 0; j < k; j++) for (int i = 0; i < k; i++) in[i][j] = reach[j][i >> 6] >> (i & 63) & 1;
    return in;
}

Proof: recording only the longest pattern suffices

If $p_i$ occurs in $p_j$ ending at position $q$, then the longest pattern ending at $q$ (shorter than $p_j$ itself when $q$ is the last position) contains $p_i$ as a suffix, and is recorded. So every containment is either recorded directly or follows from a recorded one by transitivity (substring of a substring), and every recorded edge is a true containment. Processing $j$ in increasing length order means the rows of all contained (shorter or equal) patterns are complete when row $j$ is closed, and the fixpoint loop propagates through equal-length copies. The direct edges are at most $L$, and the closure costs $O(k^3/64)$ bit operations. Checked against brute force find on random pattern sets.

Related notes

• Trie and Aho–Corasick
• Bitset (bit-parallel automata)
• FFT (correlations)