Lançado · em melhoria
Guia de Algoritmos de strings · 2/6
Por enquanto, este capítulo está disponível apenas em inglês.
This chapter traces KMP, Rabin-Karp, tries and the Z-algorithm by hand on small inputs. Working out the tables yourself makes the code in the next chapter much easier to read.
The prefix function pi[i] is the length of the longest border of the first i + 1 characters of the pattern (p[0..i]). It is also called the failure function or failure table. Here it is for ababaca.
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| p[i] | a | b | a | b | a | c | a |
| pi[i] | 0 | 0 | 1 | 2 | 3 | 0 | 1 |
The computation runs left to right and carries k, the border length at the previous position.
i = 1: p[1] = b differs from p[0] = a and k = 0, so pi[1] = 0.i = 2: p[2] = a equals p[0], so k = 1 and pi[2] = 1.i = 3, 4: the characters keep matching and k grows to 2, then 3.i = 5: p[5] = c differs from p[3] = b. Instead of starting over, fall back to a shorter border: k = pi[k - 1] = pi[2] = 1. p[1] = b still differs, so k = pi[0] = 0; p[0] = a differs too, and pi[5] = 0.i = 6: p[6] = a equals p[0], so pi[6] = 1.Step 4 is the key idea. On a mismatch you jump straight to the next shorter border inside the current one. Because a border of a border is itself a border, no candidate is skipped.
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
print(prefix_function("ababaca")) # [0, 0, 1, 2, 3, 0, 1]Searching works the same way. k is the number of pattern characters matched so far, and the text pointer i never moves backwards. Search for () in :
ababpi = [0, 0, 1, 2]abababcabab| i | Char | Action | k after | Result |
|---|---|---|---|---|
| 0-3 | a b a b | all match | 4 | match at 0, k = pi[3] = 2 |
| 4 | a | matches p[2] = a | 3 | |
| 5 | b | matches p[3] = b | 4 | match at 2, k = 2 |
| 6 | c | fails against p[2], then p[0] | 0 | |
| 7-10 | a b a b | all match | 4 | match at 7 |
Setting k = pi[m - 1] after a match, instead of 0, is what finds overlapping occurrences such as the ones at 0 and 2.
Rabin-Karp compares the hash of each length-m window with the hash of the pattern. When the window slides by one, the hash is not recomputed from scratch: the leading character is removed and the new one added in O(1).
h(s) = (s[0]·B^(m-1) + s[1]·B^(m-2) + ... + s[m-1]) mod M
next window: h' = ((h - s[i]·B^(m-1))·B + s[i+m]) mod MTo keep the numbers readable, use a digit string with B = 10 and M = 11. The text is 31415926, the pattern is 1592, and the pattern hash is 1592 mod 11 = 8.
| Start | Window | Hash | Verdict |
|---|---|---|---|
| 0 | 3141 | 6 | skip |
| 1 | 1415 | 7 | skip |
| 2 | 4159 | 1 | skip |
| 3 | 1592 | 8 | characters compared: match |
| 4 | 5926 | 8 | characters compared: no match (false positive) |
As the last row shows, equal hashes do not guarantee equal strings, so a hash hit must always be confirmed by comparing characters. Real code uses a large prime modulus such as 10**9 + 7 and a random base to make collisions rare.
def window_hashes(text: str, m: int, base: int = 10, mod: int = 11) -> list[int]:
high = pow(base, m - 1, mod)
h = 0
for ch in text[:m]:
h = (h * base + int(ch)) % mod
out = [h]
for i in range(len(text) - m):
h = ((h - int(text[i]) * high) * base + int(text[i + m])) % mod
out.append(h)
return out
print(window_hashes("31415926", 4)) # [6, 7, 1, 8, 8]A trie is a tree you walk down one character at a time. After inserting car, cart, cat and dog, the common prefix ca is stored once. A * marks a node where a word ends.
(root)
├─ c ─ a ─ r* ─ t*
│ └─ t*
└─ d ─ o ─ g*To autocomplete ca, walk down c then a and collect every end-of-word mark below that node: car, cart, cat. The walk costs time proportional to the prefix length, independent of how many words the dictionary holds.
In the Z-array, z[i] is the length of the longest common prefix of s[i:] and s. For aabxaab it is [7, 1, 0, 0, 3, 1, 0] (by convention z[0] is the length or 0). To search, build the Z-array of pattern + "$" + text and report positions where the value equals m; the separator $ must not appear in either string. By reusing the rightmost interval [l, r) already matched (the Z-box), the whole array is computed in O(n + m).
k = pi[m - 1], which also finds overlapping occurrences.O(1) and confirms hash hits character by character to reject false positives.
0 comentários
Fazer login · Faça login para deixar um comentário.
Seja o primeiro a comentar.