Real-World Use

The same character can also be encoded in more than one way. é may be a single precomposed code point (U+00E9) or e followed by a combining accent. Text stored in NFD, as macOS file names often are, will not match an NFC query. For case-insensitive comparison, casefold() is more correct than lower().

import unicodedata

nfd = unicodedata.normalize("NFD", "café")
print(len("café"), len(nfd))                           # 4 5
print("café" in nfd)                                   # False
print("café" in unicodedata.normalize("NFC", nfd))     # True
print("Straße".lower() == "STRASSE".lower())          # False
print("Straße".casefold() == "STRASSE".casefold())    # True

A search pipeline should apply the same normalization and case folding when indexing and when querying.

Pitfall 2: hash collisions and hostile input

If Rabin-Karp skips the confirmation step on a hash hit, it can report wrong answers. With a fixed base and modulus an attacker can build colliding inputs, so pick a random base on each run and use a large prime modulus such as 2^61 - 1, or combine two independent hashes.

import random

MOD = (1 << 61) - 1
BASE = random.randrange(256, MOD - 1)   # different base on every run


def poly_hash(s: str) -> int:
    h = 0
    for ch in s:
        h = (h * BASE + ord(ch)) % MOD
    return h


print(poly_hash("abc") == poly_hash("abc"), poly_hash("abc") == poly_hash("acb"))
# True False (a collision is very unlikely, but never impossible)

Pitfall 3: memory and recursion

• Tries allocate many node objects and use a lot of memory. With millions of words, consider compact structures: radix trees, double-array tries, or a sorted list with binary search.
• A recursive DFS over a trie can hit Python's recursion limit on very long keys. Use an explicit stack.
• Regular expressions are convenient, but on backtracking engines patterns like (a+)+ can take exponential time (ReDoS). Escape user input with re.escape before using it as a pattern.

What to pick

Summary

• Libraries and tools use Two-Way, Boyer-Moore, Aho-Corasick, rolling hashes and tries depending on the job.
• With Unicode, agree on index units, normalization and case folding first.
• Defend against hash collisions with a random base and a confirmation step, and consider compact structures for large dictionaries.

Further reading

• String-searching algorithm (Wikipedia)
• Prefix function. Knuth-Morris-Pratt (cp-algorithms)
• Z-function and its calculation (cp-algorithms)
• String Hashing (cp-algorithms)
• Trie (Wikipedia)
• Aho-Corasick algorithm (Wikipedia)
• Unicode HOWTO (Python docs)