Advanced String Algorithms — Algorithms Course

What you'll learn

Single-pattern search was the warm-up. Real text processing needs structures that index many strings or all substrings at once: the trie, the suffix array, and Aho-Corasick for matching many patterns in one pass.

By the end you'll be able to:

Build and query a trie for prefix search
Explain what a suffix array indexes
Match many patterns simultaneously with Aho-Corasick

Tries

A trie (prefix tree) stores strings by their characters: each edge is a letter, and a path from the root spells a prefix. Shared prefixes share nodes, so lookup and insertion are O(length) — independent of how many words are stored. It's the structure behind autocomplete and spell-check:

A trie holding car, card, cat, dog

(root)
├─ c ─ a ─┬─ r •            "car"
│         │   └─ d •        "card"
│         └─ t •            "cat"
└─ d ─ o ─── g •            "dog"

• marks the end of a stored word

Trie in code

Language

trie.py

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

def insert(root, word):
    node = root
    for ch in word:
        node = node.children.setdefault(ch, TrieNode())
    node.is_end = True

def search(root, word):
    node = root
    for ch in word:
        if ch not in node.children:
            return False
        node = node.children[ch]
    return node.is_end          # True only if a word ends here

Tip

A trie answers prefix queries directly: walk to the node for the prefix, then every word in its subtree matches. That's how "type-ahead" suggestions appear instantly.

Suffix arrays

A suffix array is the sorted list of all suffixes of a string (stored as their starting indices). Because the suffixes are sorted, you can binary-search for any pattern in O(m log n), and every occurrence sits in a contiguous block. Paired with an LCP (longest-common-prefix) array, it answers a huge range of substring queries — repeats, longest repeated substring, and more.

Note

Suffix arrays can be built in O(n log n) (or even O(n)). They're the practical, memory-lean alternative to suffix trees and suffix automata, which represent the same information as a tree or a minimal automaton of all substrings.

Aho-Corasick

To search for many patterns at once, Aho-Corasick builds a trie of all patterns, then adds failure links (the KMP idea, generalized to a tree) that jump to the longest proper suffix still present in the trie. One linear scan of the text then reports every occurrence of every pattern in O(n + total pattern length + matches) — the engine behind virus scanners and keyword filters.

Recap & quick check

Key takeaways

A trie stores strings by characters; shared prefixes share nodes — O(length) operations.
Tries answer prefix queries directly, powering autocomplete and spell-check.
A suffix array is the sorted array of a string's suffixes — binary-search patterns in O(m log n).
An LCP array augments it for repeats and longest-repeated-substring queries.
Aho-Corasick matches many patterns in one linear pass using trie + failure links.

Quick check

1. What is the lookup cost in a trie?

2. A suffix array stores:

3. What does Aho-Corasick add to a trie of patterns?

4. Which problem is a trie especially good at?

From letters to numbers: the algorithms behind cryptography and number theory. Next up: Module 32 — Number-Theoretic Algorithms.