Guide Algorithmes sur les chaînes · 3/6
Ce chapitre n'est disponible qu'en anglais pour le moment.
KMP and a trie in Python, explained, then the same KMP core in C++, Java and TypeScript.
def prefix_function(p: str) -> list[int]:
pi = [0] * len(p) # pi[i]: longest border of p[:i+1]
k = 0
for i in range(1, len(p)):
while k > 0 and p[i] != p[k]: # fall back to a shorter border
k = pi[k - 1]
if p[i] == p[k]:
k += 1
pi[i] = k
return pi
def kmp_search(text: str, pattern: str) -> list[int]:
m = len(pattern)
if m == 0:
return list(range(len(text) + 1))
pi = prefix_function(pattern)
hits, k = [], 0 # k: matched so far
for i, ch in enumerate(text):
while k > 0 and ch != pattern[k]:
k = pi[k - 1]
if ch == pattern[k]:
k += 1
if k == m:
hits.append(i - m + 1)
k = pi[k - 1] # allow overlaps
return hits
assert prefix_function("ababaca") == [0, 0, 1, 2, 3, 0, 1]
assert kmp_search("abababcabab", "abab") == [0, 2, 7]
assert kmp_search("aaaa", "aa") == [0, 1, 2]while shrinks k on a mismatch, if grows it on a match; both functions share this shape.str.find; without the check, pattern[0] fails.i - m + 1 turns the match's end i into its start.class TrieNode:
def __init__(self) -> None:
self.children: dict[str, "TrieNode"] = {}
self.is_end = False
class Trie:
def __init__(self) -> None:
self.root = TrieNode()
def insert(self, word: str) -> None:
node = self.root
for ch in word:
node = node.children.setdefault(ch, TrieNode())
node.is_end = True
def _walk(self, prefix: str) -> TrieNode | None:
node = self.root
for ch in prefix:
node = node.children.get(ch)
if node is None:
return None
return node
def complete(self, prefix: str, limit: int = 10) -> list[str]:
start = self._walk(prefix)
if start is None:
return []
out: list[str] = []
stack = [(start, prefix)]
while stack and len(out) < limit:
node, word = stack.pop()
if node.is_end:
out.append(word)
for ch in sorted(node.children, reverse=True):
stack.append((node.children[ch], word + ch))
return out
t = Trie()
for w in ["car", "cart", "cat", "dog"]:
t.insert(w)
assert t.complete("ca") == ["car", "cart", "cat"]dict of children works for any alphabet; for lowercase only, 26 slots are faster.is_end, the bare prefix would be listed as a word.cacomplete uses an explicit stack; children are pushed in reverse so they pop in sorted order.#include <string>
#include <vector>
std::vector<int> prefixFunction(const std::string& p) {
std::vector<int> pi(p.size(), 0);
int k = 0;
for (size_t i = 1; i < p.size(); ++i) {
while (k > 0 && p[i] != p[k]) k = pi[k - 1];
if (p[i] == p[k]) ++k;
pi[i] = k;
}
return pi;
}
std::vector<int> kmpSearch(const std::string& text, const std::string& pattern) {
std::vector<int> hits;
const int m = static_cast<int>(pattern.size());
if (m == 0) return hits;
const std::vector<int> pi = prefixFunction(pattern);
int k = 0;
for (size_t i = 0; i < text.size(); ++i) {
while (k > 0 && text[i] != pattern[k]) k = pi[k - 1];
if (text[i] == pattern[k]) ++k;
if (k == m) {
hits.push_back(static_cast<int>(i) - m + 1);
k = pi[k - 1];
}
}
return hits;
}std::string holds bytes, so UTF-8 positions are byte offsets. An empty pattern returns nothing here.
import java.util.ArrayList;
import java.util.List;
public final class Kmp {
static int[] prefixFunction(String p) {
int[] pi = new int[p.length()];
int k = 0;
for (int i = 1; i < p.length(); i++) {
while (k > 0 && p.charAt(i) != p.charAt(k)) k = pi[k - 1];
if (p.charAt(i) == p.charAt(k)) k++;
pi[i] = k;
}
return pi;
}
static List<Integer> search(String text, String pattern) {
List<Integer> hits = new ArrayList<>();
int m = pattern.length();
if (m == 0) return hits;
int[] pi = prefixFunction(pattern);
int k = 0;
for (int i = 0; i < text.length(); i++) {
while (k > 0 && text.charAt(i) != pattern.charAt(k)) k = pi[k - 1];
if (text.charAt(i) == pattern.charAt(k)) k++;
if (k == m) {
hits.add(i - m + 1);
k = pi[k - 1];
}
}
return hits;
}
}charAt returns UTF-16 code units: matching stays exact, but positions count code units.
export function prefixFunction(p: string): number[] {
const pi = new Array<number>(p.length).fill(0);
let k = 0;
for (let i = 1; i < p.length; i++) {
while (k > 0 && p[i] !== p[k]) k = pi[k - 1];
if (p[i] === p[k]) k++;
pi[i] = k;
}
return pi;
}
export function kmpSearch(text: string, pattern: string): number[] {
const hits: number[] = [];
const m = pattern.length;
if (m === 0) return hits;
const pi = prefixFunction(pattern);
let k = 0;
for (let i = 0; i < text.length; i++) {
while (k > 0 && text[i] !== pattern[k]) k = pi[k - 1];
if (text[i] === pattern[k]) k++;
if (k === m) {
hits.push(i - m + 1);
k = pi[k - 1];
}
}
return hits;
}k on a mismatch, grow it on a match.is_end flag; autocomplete collects words below the prefix node.
0 commentaire
Se connecter · Connectez-vous pour laisser un commentaire.