Guide Algorithmes sur les chaînes · 5/6
Ce chapitre n'est disponible qu'en anglais pour le moment.
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 piYou 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") == 2Decide 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)Given a log line s and a length , find a substring of length that occurs at least twice. Among those, return the one whose second occurrence ends earliest; return an empty string if there is none.
LLApproach: 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) == ""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.
k = pi[m - 1] after a match.n - pi[n - 1], which directly answers whether a string is a repetition.
0 commentaire
Se connecter · Connectez-vous pour laisser un commentaire.