Unit 25: Words and Patterns

Turn the letters into digits

Read the string as a number in base 31: each letter is a digit, and the whole thing is worked out under a big prime modulus so it stays small.

Same string, same number, always. Different strings, almost certainly different numbers.

Python

MOD = 1000000007
BASE = 31

def string_hash(text):
    value = 0
    for ch in text:
        value = (value * BASE + ord(ch) - 96) % MOD
    return value

print(string_hash("abc"))
print(string_hash("abc") == string_hash("abc"))
print(string_hash("abc") == string_hash("acb"))

It prints

1026
True
False

Prefix hashes give you every substring at once

Store the hash of every prefix and the powers of the base. Then the hash of any slice is one subtraction and one multiply — the same trick as unit 6's prefix sums, with multiplication instead of addition.

So comparing two substrings of any length costs the same as comparing two numbers.

Python

MOD = 1000000007
BASE = 31
text = "abcabc"
n = len(text)

prefix = [0] * (n + 1)
power = [1] * (n + 1)
for i in range(n):
    prefix[i + 1] = (prefix[i] * BASE + ord(text[i]) - 96) % MOD
    power[i + 1] = power[i] * BASE % MOD

def slice_hash(start, length):
    return (prefix[start + length] - prefix[start] * power[length]) % MOD

print(slice_hash(0, 3), slice_hash(3, 3))
print(slice_hash(0, 3) == slice_hash(3, 3))
print(slice_hash(0, 2) == slice_hash(1, 2))

It prints

1026 1026
True
False

The honest warning

Two different strings can land on the same number. With a modulus near a thousand million it is vanishingly unlikely; with a small one it happens almost at once.

Under a modulus of 101 it takes only a few dozen two-letter words to find aa and di sharing the number 32. That is exactly what a problem setter does when they want to break hash solutions.

Python

SMALL = 101
BASE = 31

def small_hash(text):
    value = 0
    for ch in text:
        value = (value * BASE + ord(ch) - 96) % SMALL
    return value

seen = {}
for a in range(26):
    for b in range(26):
        word = chr(97 + a) + chr(97 + b)
        h = small_hash(word)
        if h in seen:
            print(seen[h], word, h)
            break
        seen[h] = word
    else:
        continue
    break

It prints

aa di 32

So what does a hash answer mean?

It means "these are equal, with a chance of being wrong of about one in a thousand million". For a contest that is fine, and it is what nearly everybody submits.

If a problem is famous for anti-hash tests, use two moduli at once — the chance of colliding under both is one in a very large number indeed.

How much of the start is also the end?

For each position, find the longest piece that is both a beginning and an ending of the string up to there — not counting the whole thing.

For abcabca the answer at the end is 4: abca starts it and finishes it. This list is called the prefix function.

Python

def prefix_function(text):
    n = len(text)
    result = [0] * n
    k = 0
    for i in range(1, n):
        while k > 0 and text[i] != text[k]:
            k = result[k - 1]
        if text[i] == text[k]:
            k += 1
        result[i] = k
    return result

print(prefix_function("abcabca"))
print(prefix_function("aaaa"))
print(prefix_function("abcdef"))

It prints

[0, 0, 0, 1, 2, 3, 4]
[0, 1, 2, 3]
[0, 0, 0, 0, 0, 0]

Why it is fast

The inner while looks alarming. But k goes up by at most one per letter and the while only ever pushes it down, so over the whole string it cannot fall more than it rose.

That is unit 4's two-pointer argument again: count the total moves, not the moves per round. The whole thing is O(n).

And now search: glue the two together

To find abc inside a long text, run the prefix function on abc#thetext — with a separator that appears in neither.

Wherever the value reaches the length of the pattern, the pattern ends there. This is KMP, and it never backs up over the text.

Python

def prefix_function(text):
    n = len(text)
    result = [0] * n
    k = 0
    for i in range(1, n):
        while k > 0 and text[i] != text[k]:
            k = result[k - 1]
        if text[i] == text[k]:
            k += 1
        result[i] = k
    return result

pattern = "abc"
text = "xabcyabc"
joined = pattern + "#" + text
values = prefix_function(joined)

found = []
for i in range(len(joined)):
    if values[i] == len(pattern):
        found.append(i - 2 * len(pattern))

print(values)
print(found)

It prints

[0, 0, 0, 0, 0, 1, 2, 3, 0, 1, 2, 3]
[1, 5]

Why the separator has to be there

Without it, a match could straddle the join — the end of the pattern and the start of the text pretending to be one piece.

The separator must be a character that appears in neither string. If the input can contain anything, hash instead.

One tree for a whole dictionary

A trie stores words by their letters: the root is empty, and every step down adds a letter. Words sharing a start share a branch.

Looking a word up costs its own length, whether the dictionary holds ten words or ten million.

Python

words = ["cat", "car", "cart", "dog"]

children = [{}]
ended = [False]

for word in words:
    node = 0
    for ch in word:
        if ch not in children[node]:
            children.append({})
            ended.append(False)
            children[node][ch] = len(children) - 1
        node = children[node][ch]
    ended[node] = True

print(len(children))
print(sorted(children[0].keys()))

It prints

9
['c', 'd']

Nine nodes for four words

Sixteen letters, nine nodes: cat, car and cart share ca, and cart is car with one more step.

That sharing is the point. A dictionary of a hundred thousand words has far fewer nodes than letters.

Looking things up

Walk down one letter at a time. Fall off the tree and the word is not there; land on a node marked as an ending and it is.

And a node not marked as an ending still tells you something useful: car is a real word, ca is only a prefix.

Python

words = ["cat", "car", "cart", "dog"]
children = [{}]
ended = [False]
for word in words:
    node = 0
    for ch in word:
        if ch not in children[node]:
            children.append({})
            ended.append(False)
            children[node][ch] = len(children) - 1
        node = children[node][ch]
    ended[node] = True

def find(word):
    node = 0
    for ch in word:
        if ch not in children[node]:
            return "missing"
        node = children[node][ch]
    return "word" if ended[node] else "prefix only"

for word in ["car", "cart", "ca", "cab", "dog"]:
    print(word, find(word))

It prints

car word
cart word
ca prefix only
cab missing
dog word

What tries are actually used for

Autocomplete, spell checking, and any problem shaped like "for each of these words, is it in that pile" — where hashing works too, but a trie also answers questions about prefixes that a hash cannot.

A trie of the binary digits of numbers also answers "which stored number gives the biggest xor with this one", which is a classic contest problem.

The same search, three times over

Find every place a pattern appears in a text. Naively — compare at every position, letter by letter. By hashing — one number comparison per position. By KMP — one pass, never looking back.

All three give the same answer. Only the counting is different, and this is where the track finishes.

Counting the comparisons

On a text of aaaaaaaaaa and a pattern of aaa, the naive search compares 24 letters. Hashing compares 8 numbers. KMP walks the joined string once.

The naive one is fine here and dies on the case problem setters love: a long text and a pattern that nearly matches everywhere.

Python

text = "aaaaaaaaaa"
pattern = "aaa"

steps = 0
found = []
for start in range(len(text) - len(pattern) + 1):
    ok = True
    for i in range(len(pattern)):
        steps += 1
        if text[start + i] != pattern[i]:
            ok = False
            break
    if ok:
        found.append(start)

print(found)
print(steps)

It prints

[0, 1, 2, 3, 4, 5, 6, 7]
24

The hashed version

Work out the pattern's hash once and every window's hash from the prefix table. Eight comparisons, each of one number, whatever the pattern's length.

Same eight positions found.

Python

MOD = 1000000007
BASE = 31
text = "aaaaaaaaaa"
pattern = "aaa"
n = len(text)
m = len(pattern)

prefix = [0] * (n + 1)
power = [1] * (n + 1)
for i in range(n):
    prefix[i + 1] = (prefix[i] * BASE + ord(text[i]) - 96) % MOD
    power[i + 1] = power[i] * BASE % MOD

wanted = 0
for ch in pattern:
    wanted = (wanted * BASE + ord(ch) - 96) % MOD

steps = 0
found = []
for start in range(n - m + 1):
    steps += 1
    value = (prefix[start + m] - prefix[start] * power[m]) % MOD
    if value == wanted:
        found.append(start)

print(found)
print(steps)

It prints

[0, 1, 2, 3, 4, 5, 6, 7]
8

And KMP, which never guesses

KMP is the only one of the three that is both fast and certain — hashing could in principle collide, and the naive version could in principle take n * m steps.

It is also the fiddliest to type from memory, which is why most contestants hash first and reach for this when the setter has clearly gone hunting.

Python

def matches(pattern, text):
    joined = pattern + "#" + text
    n = len(joined)
    values = [0] * n
    k = 0
    for i in range(1, n):
        while k > 0 and joined[i] != joined[k]:
            k = values[k - 1]
        if joined[i] == joined[k]:
            k += 1
        values[i] = k
    out = []
    for i in range(n):
        if values[i] == len(pattern):
            out.append(i - 2 * len(pattern))
    return out

print(matches("aaa", "aaaaaaaaaa"))
print(matches("abc", "xabcyabc"))
print(matches("zz", "abcabc"))

It prints

[0, 1, 2, 3, 4, 5, 6, 7]
[1, 5]
[]

Which to reach for

Hash it. It is short, it is fast, it handles "are these two substrings the same" as easily as searching, and it is what most people submit.

Use KMP when a wrong answer from a collision would be fatal, or when the problem is about the prefix function itself — "what is the shortest piece this string is made of by repeating" is a one-line answer from it.