Algebraic, Randomized, Dynamic & Multidimensional Methods

Convolution for Matching

Convolution converts alignment comparisons into coefficient arithmetic. For each symbol $c$, let $T_c[i]=1$ when text position $i$ contains $c$, and let $P_c[m-1-j]=1$ when pattern position $j$ contains $c$. Then $(T_c*P_c)[i+m-1]$ counts positions where both aligned symbols equal $c$. Summing over the alphabet gives the agreement count; without wildcards, the Hamming distance is $m$ minus that count.

For wildcard matching, omit wildcard positions from every pattern indicator. If the pattern has $k$ concrete positions, an alignment is valid exactly when its agreement count is $k$. One transform per distinct pattern symbol costs $O(\sigma N\log N)$ for combined length $N$. Algebraic encodings can reduce the number of transforms, while an NTT gives exact modular coefficients when its modulus supports the transform length.

MODULUS = 998_244_353
PRIMITIVE_ROOT = 3


def ntt(values: list[int], invert: bool) -> None:
    n = len(values)
    j = 0
    for i in range(1, n):
        bit = n >> 1
        while j & bit:
            j ^= bit
            bit >>= 1
        j ^= bit
        if i < j:
            values[i], values[j] = values[j], values[i]

    length = 2
    while length <= n:
        root = pow(PRIMITIVE_ROOT, (MODULUS - 1) // length, MODULUS)
        if invert:
            root = pow(root, MODULUS - 2, MODULUS)
        half = length // 2
        for start in range(0, n, length):
            factor = 1
            for offset in range(half):
                even = values[start + offset]
                odd = values[start + offset + half] * factor % MODULUS
                values[start + offset] = (even + odd) % MODULUS
                values[start + offset + half] = (even - odd) % MODULUS
                factor = factor * root % MODULUS
        length <<= 1

    if invert:
        inverse_n = pow(n, MODULUS - 2, MODULUS)
        for i in range(n):
            values[i] = values[i] * inverse_n % MODULUS


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 (MODULUS - 1) % size:
        raise ValueError("transform length unsupported by modulus")
    a = left + [0] * (size - len(left))
    b = right + [0] * (size - len(right))
    ntt(a, False)
    ntt(b, False)
    for i in range(size):
        a[i] = a[i] * b[i] % MODULUS
    ntt(a, True)
    return a[:result_length]


def wildcard_matches(text: str, pattern: str, wildcard: str = "?") -> list[int]:
    """Return starts where every concrete pattern symbol matches."""
    n, m = len(text), len(pattern)
    if m == 0:
        return list(range(n + 1))
    if m > n:
        return []

    symbols = sorted({c for c in pattern if c != wildcard})
    concrete_count = sum(c != wildcard for c in pattern)
    agreement = [0] * (n + m - 1)

    for symbol in symbols:
        text_vector = [int(c == symbol) for c in text]
        pattern_vector = [int(c == symbol) for c in reversed(pattern)]
        product = convolution(text_vector, pattern_vector)
        for i, value in enumerate(product):
            agreement[i] += value

    return [
        start
        for start in range(n - m + 1)
        if agreement[start + m - 1] == concrete_count
    ]


if __name__ == "__main__":
    assert wildcard_matches("abracadabra", "a?a") == [3, 5]
    assert wildcard_matches("ACGTACGT", "A?G") == [0, 4]
    assert wildcard_matches("anything", "???") == list(range(6))
    assert wildcard_matches("short", "a-much-longer-pattern") == []
    print(wildcard_matches("bananana", "b?n"))

Randomized Fingerprints and Streaming Equality

A Karp–Rabin fingerprint treats a string as a polynomial: $H(S)=\sum_{i=0}^{m-1}s_i b^{m-1-i}\pmod p$. Prefix hashes and powers extract equal-length substring hashes in $O(1)$ after linear preprocessing, while a rolling window removes the outgoing contribution, multiplies by $b$, and adds the incoming symbol.

Equal strings always hash equally; unequal strings may collide. If the compared length is at most $L$ and $b$ is random in $\mathbb F_p$, their nonzero difference polynomial has at most $L-1$ roots, so one comparison collides with probability at most $(L-1)/p$. Across $Q$ comparisons, the union bound is $Q(L-1)/p$. Independent moduli or bases multiply the per-comparison probabilities.

Hash-only equality is Monte Carlo. A Las Vegas design verifies candidates against the original symbols and is always correct, with randomness affecting runtime only. Streaming hashes retain only a polynomial state; linear sketches extend this idea to mismatch estimation, reconciliation, and compact communication.

Dynamic and Persistent Strings

Static prefix hashes break under insertion or deletion because later indices shift. A dynamic string instead uses an implicit balanced tree or rope. Each node stores subtree length and a composable hash, with concatenation $H(XY)=H(X)b^{|Y|}+H(Y)\pmod p$. Splits and joins support insertion, deletion, concatenation, and substring isolation in logarithmic time.

Point replacement changes one leaf and recomputes aggregates along a root path. Maintaining forward and reverse hashes supports palindrome queries and lazy reversals. For fixed-length arrays with point updates, Fenwick and segment trees can maintain weighted character contributions, though insertions favor implicit trees.

Ropes store chunks at leaves for cache locality. Persistent path copying creates a new root per edit while sharing untouched subtrees, enabling historical queries, undo, and branches with $O(\log n)$ new nodes per update. Hashes remain probabilistic, so store lengths, use independent moduli when justified, and verify security-sensitive equality.

flowchart TD
    EDIT["Edit position i"]
    DESCEND["Descend using subtree lengths"]
    LEAF["Replace or split leaf chunk"]
    REHASH["Recompute length and forward/reverse hashes"]
    SHARE["Share untouched persistent subtrees"]
    ROOT["New root represents edited string"]
    EDIT --> DESCEND
    DESCEND --> LEAF
    LEAF --> REHASH
    REHASH -->|"update ancestors"| ROOT
    REHASH -->|"path copying"| SHARE
    SHARE --> ROOT

Multidimensional and Structured Sequences

For grids, a two-dimensional polynomial hash uses independent row and column weights; a 2D prefix table extracts rectangular hashes in constant time. Separable matching processes rows first and then matches the sequence of row results vertically, while 2D convolution counts aligned cell agreements.

A circular string is represented by $S+S$, restricting valid rotation starts to $[0,n)$. Ordered trees can be serialized with explicit boundaries; unordered trees need canonical child ordering or multiset hashing. Token streams should be normalized to stable integer IDs before applying hashes, suffix structures, LCS, or edit distance.

Numerical sequences may require adjacent differences, ranks, quantization, or tolerance-aware comparison to capture the intended invariance. DNA supports two-bit packing for A, C, G, and T, but ambiguous IUPAC symbols need masks, and reverse-complement search must apply biological complement rules.

External-Memory and Hardware-Aware Processing

A streaming matcher must preserve state across chunks. KMP can carry its automaton state directly. A stateless matcher can prepend the previous chunk's last $m-1$ symbols to the next chunk so every length-$m$ boundary-spanning occurrence is visible, then deduplicate starts assigned to the overlap.

Packed alphabets reduce memory traffic: DNA fits in two bits, byte classes fit masks, and bitsets process $w$ positions per word. Shift-Or, Myers edit matching, bitset LCS, and population-count Hamming distance turn many scalar operations into word operations. SIMD adds lane parallelism but must handle unaligned prefixes, tails, and cross-vector matches.

Parallel text blocks require sufficient overlap or explicit transfer of automaton boundary states. For external memory, sequential scans, blocked indexes, buffering, compressed postings, and cache-aware layouts minimize I/O. Chunk size balances overlap overhead, decompression granularity, parallelism, cache capacity, and storage latency.