FFT-Based Wildcard Matching

Matching as Correlation

Let text $T$ have length $n$ and pattern $P$ have length $m\le n$. At alignment $s$, pattern position $j$ is compared with text position $s+j$. This is a cross-correlation. Polynomial multiplication uses index sums, so reverse the pattern vector: $P^R[k]=P[m-1-k]$. Then convolution coefficient $C[s+m-1]$ contains exactly the products for alignment $s$:

$$ C[s+m-1]=\sum_{j=0}^{m-1}T[s+j]P[j]. $$

This reversal is the central indexing trick. Once compatibility is expressed as a sum of coefficient products, one convolution evaluates every complete alignment simultaneously.

An Algebraic Wildcard Identity

Assign each ordinary symbol a distinct positive integer and encode a wildcard as zero. For encoded symbols $x$ and $y$, define $g(x,y)=xy(x-y)^2$. It vanishes exactly when $x=0$, $y=0$, or $x=y$; for positive unequal codes it is strictly positive. Therefore alignment $s$ is compatible exactly when

$$ G[s]=\sum_{j=0}^{m-1}T_{s+j}P_j(T_{s+j}-P_j)^2=0. $$

Expanding gives three correlations:

$$ G[s]=\sum_jT_{s+j}^3P_j-2\sum_jT_{s+j}^2P_j^2+\sum_jT_{s+j}P_j^3. $$

After reversing the pattern vectors, three convolutions evaluate every alignment without multiplying the running time by alphabet size.

With distinct positive codes and zero reserved exclusively for wildcards, $G[s]=0$ over the integers if and only if every aligned pair is compatible. Modular implementations must prove scores cannot wrap to zero, reconstruct with enough NTT primes, or verify zero candidates deterministically.

FFT and NTT Implementation

A complex FFT computes each convolution in $O(N\log N)$ time but requires a rounding-error bound. An NTT performs exact finite-field arithmetic. The implementation below uses $998244353=119\cdot2^{23}+1$ and primitive root 3. It rejects transforms beyond $2^{23}$ and inputs whose maximum score $m\sigma^2(\sigma-1)^2$ could reach the modulus; under that bound, modular zero is equivalent to integer zero.

MOD = 998_244_353
ROOT = 3
MAX_N = 1 << 23


def ntt(a: list[int], invert: bool) -> None:
    n = len(a)
    if n == 0 or n & (n - 1) or n > MAX_N:
        raise ValueError("unsupported NTT length")
    j = 0
    for i in range(1, n):
        bit = n >> 1
        while j & bit:
            j ^= bit
            bit >>= 1
        j ^= bit
        if i < j:
            a[i], a[j] = a[j], a[i]
    length = 2
    while length <= n:
        wlen = pow(ROOT, (MOD - 1) // length, MOD)
        if invert:
            wlen = pow(wlen, MOD - 2, MOD)
        half = length // 2
        for start in range(0, n, length):
            w = 1
            for offset in range(half):
                u = a[start + offset]
                v = a[start + offset + half] * w % MOD
                a[start + offset] = (u + v) % MOD
                a[start + offset + half] = (u - v) % MOD
                w = w * wlen % MOD
        length <<= 1
    if invert:
        inverse_n = pow(n, MOD - 2, MOD)
        for i in range(n):
            a[i] = a[i] * inverse_n % MOD


def convolution(left: list[int], right: list[int]) -> list[int]:
    if not left or not right:
        return []
    result_length = len(left) + len(right) - 1
    size = 1
    while size < result_length:
        size <<= 1
    if size > MAX_N:
        raise ValueError("convolution exceeds the modulus root order")
    a = [x % MOD for x in left] + [0] * (size - len(left))
    b = [x % MOD for x in right] + [0] * (size - len(right))
    ntt(a, False)
    ntt(b, False)
    for i in range(size):
        a[i] = a[i] * b[i] % MOD
    ntt(a, True)
    return a[:result_length]


def wildcard_matches(text: str, pattern: str, wildcard: str = "?") -> list[int]:
    n, m = len(text), len(pattern)
    if m == 0:
        return list(range(n + 1))
    if m > n:
        return []
    if len(wildcard) != 1:
        raise ValueError("wildcard must be one character")

    alphabet = sorted((set(text) | set(pattern)) - {wildcard})
    codes = {symbol: index + 1 for index, symbol in enumerate(alphabet)}
    sigma = len(alphabet)
    if m * sigma**2 * max(0, sigma - 1) ** 2 >= MOD:
        raise ValueError("score may wrap; use more primes or verify candidates")

    t = [0 if c == wildcard else codes[c] for c in text]
    p = [0 if c == wildcard else codes[c] for c in pattern][::-1]
    c1 = convolution([x**3 for x in t], p)
    c2 = convolution([x**2 for x in t], [y**2 for y in p])
    c3 = convolution(t, [y**3 for y in p])

    answer = []
    for start in range(n - m + 1):
        k = start + m - 1
        if (c1[k] - 2 * c2[k] + c3[k]) % MOD == 0:
            answer.append(start)
    return answer


def naive(text: str, pattern: str, wildcard: str = "?") -> list[int]:
    if not pattern:
        return list(range(len(text) + 1))
    return [
        start
        for start in range(len(text) - len(pattern) + 1)
        if all(
            a == wildcard or b == wildcard or a == b
            for a, b in zip(text[start:start + len(pattern)], pattern)
        )
    ]


if __name__ == "__main__":
    examples = [
        ("abracadabra", "a?a"),
        ("abcxabcdabxabcdabcdabcy", "abcd?bcy"),
        ("A?CGTACG?", "AC?G"),
        ("aaaaaa", "a?a"),
        ("xyz", ""),
        ("ab", "abc"),
    ]
    for text, pattern in examples:
        assert wildcard_matches(text, pattern) == naive(text, pattern)

    from itertools import product
    for n in range(5):
        for m in range(4):
            for text_tuple in product("ab?", repeat=n):
                text = "".join(text_tuple)
                for pattern_tuple in product("ab?", repeat=m):
                    pattern = "".join(pattern_tuple)
                    assert wildcard_matches(text, pattern) == naive(text, pattern)

Complexity, Precision, and Alternatives

The algebraic method performs three convolutions of length $O(n+m)$, using $O(N\log N)$ arithmetic and $O(N)$ storage. Its cost is independent of alphabet size, but transform constants and correctness controls matter. Per-symbol indicator convolutions are simpler for tiny alphabets and directly yield Hamming mismatch counts. Bitsets usually win for moderate patterns, while hashes and q-gram filters are attractive when only a few candidates require verification.

Method	Best-fit alphabet and length	Wildcard support	Mismatch output	Correctness model	Typical cost
Three-convolution NTT	Large alphabet and long offline inputs	Either sequence via code zero	Exact compatibility zero-test	Exact with a coefficient bound or enough CRT primes	$O(N\log N)$ modular operations
Complex FFT identity	Large alphabet and long inputs	Either sequence	Algebraic score	Floating-point rounding must be bounded or candidates verified	$O(N\log N)$ floating-point operations
Per-symbol convolutions	Tiny or moderate alphabet	Omit unconstrained positions	Exact constrained Hamming count	Exact with NTT; rounded integers with FFT	$O(\sigma N\log N)$ without packing
Machine-word bitsets	Small encoded alphabet and moderate pattern	Direct compatibility masks	Exact Hamming thresholds	Deterministic integer operations	$O(n\lceil m/w\rceil)$ word operations
Shift-Or or Bitap	Short patterns and small threshold	Natural wildcard masks	Exact or bounded-error matching	Deterministic within its word model	$O(n\lceil m/w\rceil)$
Rolling fingerprints	Long text with few expected candidates	Split into fixed fragments	Equality filter	Monte Carlo unless candidates are verified	$O(n+m)$ expected preprocessing and scan
Pigeonhole or q-gram filter	Small mismatch or edit threshold	Split around wildcard regions	Candidate filter	Deterministic under its partition guarantee	Often near linear; data-dependent
Naive verification	Short inputs or few candidates	Trivial	Exact mismatches and witnesses	Fully deterministic	$O(nm)$ without filtering

Cookie Consent

FFT-Based Wildcard Matching

Table of Contents

Matching as Correlation

An Algebraic Wildcard Identity

FFT and NTT Implementation

Complexity, Precision, and Alternatives