Rabin–Karp and Aho–Corasick

Rabin–Karp compares fixed-length windows with a rolling hash: remove the old character contribution, shift by the base, add the new character and reduce modulo. Equal hashes are not proof of equality. Direct verification restores deterministic correctness but may increase worst-case cost; double hashing reduces rather than eliminates collision risk.

Aho–Corasick stores many patterns in a trie and follows failure links to the longest viable suffix. Output links report suffix patterns that would otherwise be missed. BFS constructs failure states in dependency order.

Pattern lengths, alphabet representation and output count shape costs. Text filtering also requires normalisation and boundary policies; the algorithm does not determine linguistic semantics.

def rolling_hashes(text, width, base=257, mod=1000000007):
    if not 1 <= width <= len(text): return []
    high=pow(base,width-1,mod); h=0
    for c in text[:width]: h=(h*base+ord(c))%mod
    result=[h]
    for i in range(width,len(text)):
        h=((h-ord(text[i-width])*high)*base+ord(text[i]))%mod
        result.append(h)
    return result
assert len(rolling_hashes("ababa",3)) == 3