Practice Problems

These exercises were written to apply the prefix function, rolling hashes and tries from the earlier chapters. For each one, think of the naive solution first, find the slow part, then swap in the right tool. The prefix_function used below is the same as in the implementation chapter.

def prefix_function(p: str) -> list[int]:
    pi = [0] * len(p)
    k = 0
    for i in range(1, len(p)):
        while k > 0 and p[i] != p[k]:
            k = pi[k - 1]
        if p[i] == p[k]:
            k += 1
        pi[i] = k
    return pi

Problem 1. Counting overlapping motifs

You are given a DNA sequence seq (up to one million characters) and a motif motif. Count how many times the motif occurs in the sequence, counting overlapping occurrences separately. For seq = "AAAA" and motif = "AA" the answer is 3.

Approach: Python's str.count only counts non-overlapping occurrences and would return 2. Scanning with KMP and continuing with k = pi[m - 1] after each match counts overlaps too, in O(n + m).

def count_overlapping(seq: str, motif: str) -> int:
    pi = prefix_function(motif)
    m, k, count = len(motif), 0, 0
    for ch in seq:
        while k > 0 and ch != motif[k]:
            k = pi[k - 1]
        if ch == motif[k]:
            k += 1
        if k == m:
            count += 1
            k = pi[k - 1]
    return count


assert count_overlapping("AAAA", "AA") == 3
assert count_overlapping("ACGTACGTAC", "GTA") == 2

Problem 2. Finding the repeating unit

Decide whether a string s is some string u repeated two or more times. If so, return the shortest u and the repeat count; otherwise return None. For example "xyzxyzxyz" gives ("xyz", 3) and "xyzxy" gives None.

Approach: if the longest border of a string of length n has length b = pi[n - 1], then p = n - b is the smallest period of the string. When p < n and n is divisible by p, the first p characters repeat exactly n / p times.

def repeating_unit(s: str) -> tuple[str, int] | None:
    if not s:
        return None
    n = len(s)
    p = n - prefix_function(s)[-1]
    if p < n and n % p == 0:
        return s[:p], n // p
    return None


assert repeating_unit("xyzxyzxyz") == ("xyz", 3)
assert repeating_unit("xyzxy") is None
assert repeating_unit("aaaa") == ("a", 4)

Problem 3. The first repeated chunk

Given a log line s and a length L, find a substring of length L that occurs at least twice. Among those, return the one whose second occurrence ends earliest; return an empty string if there is none.

Approach: storing every slice in a set costs O(n·L) memory. Instead, roll a hash across the windows, store only the hash values in a dictionary, and when a hash repeats, compare the actual strings to confirm. A random base defends against deliberately colliding input.

import random


def first_repeat(s: str, L: int) -> str:
    if L <= 0 or L > len(s):
        return ""
    mod = (1 << 61) - 1
    base = random.randrange(256, mod - 1)
    high = pow(base, L - 1, mod)
    h = 0
    for ch in s[:L]:
        h = (h * base + ord(ch)) % mod
    seen: dict[int, list[int]] = {h: [0]}
    for i in range(1, len(s) - L + 1):
        h = ((h - ord(s[i - 1]) * high) * base + ord(s[i + L - 1])) % mod
        for j in seen.get(h, []):
            if s[j:j + L] == s[i:i + L]:
                return s[i:i + L]
        seen.setdefault(h, []).append(i)
    return ""


assert first_repeat("abcXabcY", 3) == "abc"
assert first_repeat("abcdef", 2) == ""

Problem 4. Popularity-ranked autocomplete

You are given search queries with their counts. For a typed prefix, return up to three queries that start with it, most frequent first; ties go to the lexicographically smaller query.

Approach: store the count on each end-of-word node of a trie. Walk down to the prefix node, collect every word below it, and pick the top three by (-count, query). If there are very many lookups, precompute the top three at every node instead.

import heapq


def build(queries: dict[str, int]) -> dict:
    root: dict = {}
    for q, cnt in queries.items():
        node = root
        for ch in q:
            node = node.setdefault(ch, {})
        node["$"] = cnt                     # "$" marks the end of a word
    return root


def suggest(root: dict, prefix: str, k: int = 3) -> list[str]:
    node = root
    for ch in prefix:
        if ch not in node:
            return []
        node = node[ch]
    found, stack = [], [(node, prefix)]
    while stack:
        cur, word = stack.pop()
        for key, child in cur.items():
            if key == "$":
                found.append((-child, word))
            else:
                stack.append((child, word + key))
    return [w for _, w in heapq.nsmallest(k, found)]


root = build({"python": 50, "pytest": 30, "pyenv": 30, "pandas": 70, "pip": 10})
assert suggest(root, "py") == ["python", "pyenv", "pytest"]
assert suggest(root, "p") == ["pandas", "python", "pyenv"]
assert suggest(root, "z") == []

If queries may contain the $ character, keep the end-of-word marker in a separate field.

Summary

• Overlapping occurrences are counted by continuing with k = pi[m - 1] after a match.
• The smallest period is n - pi[n - 1], which directly answers whether a string is a repetition.
• Rolling hashes compare substrings without slicing them; always confirm when hashes match.
• Storing extra data (such as counts) on trie nodes lets autocomplete rank its suggestions.