# Generated from the published Markdown; run scripts/build_language_examples.py to refresh.
# Independent examples may reuse top-level names. Python remains the explanation language.


# topics/strings/string-model.md
import unicodedata

composed = "é"
decomposed = "e\u0301"
assert composed != decomposed
assert unicodedata.normalize("NFC", composed) == unicodedata.normalize("NFC", decomposed)

# topics/strings/trie-representation.md
class TrieNode:
    def __init__(self):
        self.children = {}
        self.terminal = False

# topics/strings/trie-operations.md
class Trie:
    def __init__(self):
        self.root = TrieNode()
        self.size = 0

    def __len__(self):
        return self.size

    def is_empty(self):
        return self.size == 0

    def _walk(self, text):
        if not isinstance(text, str):
            raise TypeError("expected a string")
        node = self.root
        for char in text:
            node = node.children.get(char)
            if node is None:
                return None
        return node

    def contains(self, word):
        node = self._walk(word)
        return node is not None and node.terminal

    def has_prefix(self, prefix):
        return self._walk(prefix) is not None

    def insert(self, word):
        if not isinstance(word, str):
            raise TypeError("expected a string")
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        if node.terminal:
            return False
        node.terminal = True
        self.size += 1
        return True

    def delete(self, word):
        if not isinstance(word, str):
            raise TypeError("expected a string")
        node = self.root
        path = []
        for char in word:
            child = node.children.get(char)
            if child is None:
                return False
            path.append((node, char, child))
            node = child
        if not node.terminal:
            return False
        node.terminal = False
        self.size -= 1
        for parent, char, child in reversed(path):
            if child.terminal or child.children:
                break
            del parent.children[char]
        return True

# topics/strings/trie-operations.md
trie = Trie()
for word in ["be", "bus", "buses", "busy", "car"]:
    trie.insert(word)

# topics/strings/trie-prefix-queries.md
def words_with_prefix(trie, prefix):
    node = trie._walk(prefix)
    if node is None:
        return
    path = list(prefix)
    if node.terminal:
        yield prefix
    stack = [(node, iter(node.children.items()))]
    while stack:
        try:
            char, child = next(stack[-1][1])
        except StopIteration:
            stack.pop()
            if stack:
                path.pop()
            continue
        path.append(char)
        if child.terminal:
            yield "".join(path)
        stack.append((child, iter(child.children.items())))

# topics/strings/trie-prefix-queries.md
def longest_stored_prefix(trie, text):
    if not isinstance(text, str):
        raise TypeError("expected a string")
    node = trie.root
    best = 0 if node.terminal else None
    for i, char in enumerate(text):
        node = node.children.get(char)
        if node is None:
            break
        if node.terminal:
            best = i + 1
    return None if best is None else text[:best]

# topics/strings/substring-baseline.md
def naive_find_all(text, pattern):
    n, m = len(text), len(pattern)
    if m == 0:
        return list(range(n + 1))
    matches = []
    for start in range(n - m + 1):
        j = 0
        while j < m and text[start + j] == pattern[j]:
            j += 1
        if j == m:
            matches.append(start)
    return matches

# topics/strings/kmp-matching.md
def prefix_function(pattern):
    pi = [0] * len(pattern)
    j = 0
    for i in range(1, len(pattern)):
        while j > 0 and pattern[i] != pattern[j]:
            j = pi[j - 1]
        if pattern[i] == pattern[j]:
            j += 1
        pi[i] = j
    return pi

# topics/strings/kmp-matching.md
def kmp_find_all(text, pattern):
    if not pattern:
        return list(range(len(text) + 1))
    pi = prefix_function(pattern)
    matches = []
    j = 0
    for i, char in enumerate(text):
        while j > 0 and char != pattern[j]:
            j = pi[j - 1]
        if char == pattern[j]:
            j += 1
        if j == len(pattern):
            matches.append(i - len(pattern) + 1)
            j = pi[j - 1]
    return matches

# topics/strings/rolling-hash-search.md
def rolling_find_all(text, pattern, *, base=257, modulus=1_000_000_007):
    if type(base) is not int or base < 2:
        raise ValueError("base must be an integer at least 2")
    if type(modulus) is not int or modulus < 2:
        raise ValueError("modulus must be an integer at least 2")
    n, m = len(text), len(pattern)
    if m == 0:
        return list(range(n + 1))
    if m > n:
        return []
    high = pow(base, m - 1, modulus)
    target_hash = window_hash = 0
    for j in range(m):
        target_hash = (target_hash * base + ord(pattern[j])) % modulus
        window_hash = (window_hash * base + ord(text[j])) % modulus
    matches = []
    for start in range(n - m + 1):
        if window_hash == target_hash:
            if all(text[start + j] == pattern[j] for j in range(m)):
                matches.append(start)
        if start + m < n:
            outgoing = ord(text[start])
            incoming = ord(text[start + m])
            window_hash = ((window_hash - outgoing * high) * base
                           + incoming) % modulus
    return matches