Minden mintát helyezz el egy prefixfában, ahol minden karakter egy él, és az utak a minták végeit jelölik.
BuildAutomaton(patterns): 1. Hozz létre egy üres prefixfát (trie) 2. Minden mintát helyezz el a prefixfában 3. Hozz létre hibaszálakat: - Sorban állítsd be minden csomópont hibaszálát - A gyökér hibaszála a gyökérre mutat
Search(text, automaton): állapot = automaton.gyökér minden karakter a text-ben: amíg nincs átmenet az állapotból: állapot = állapot.hibaszála állapot = állapot.következő(karakter) ha állapot egy végállapot: jegyezd fel a találatot
from collections import deque, defaultdict
class AhoCorasick:
def __init__(self):
self.trie = defaultdict(dict)
self.fail = {}
self.output = defaultdict(list)
self.root = 0
self.state_count = 1
def build_trie(self, patterns):
for pattern in patterns:
state = self.root
for char in pattern:
if char not in self.trie:
self.trie = self.state_count
self.state_count += 1
state = self.trie
self.output.append(pattern)
def build_automaton(self):
queue = deque()
for char, next_state in self.trie.items():
self.fail = self.root
queue.append(next_state)
while queue:
state = queue.popleft()
for char, next_state in self.trie.items():
queue.append(next_state)
fail_state = self.fail
while fail_state != self.root and char not in self.trie:
fail_state = self.fail
self.fail = self.trie.get(char, self.root)
self.output.extend(self.output])
def search(self, text):
state = self.root
matches =
for i, char in enumerate(text):
while state != self.root and char not in self.trie:
state = self.fail
state = self.trie.get(char, self.root)
if self.output:
for pattern in self.output:
matches.append((i - len(pattern) + 1, pattern))
return matches
# Példa használat
patterns =
text = "ushers"
ac = AhoCorasick()
ac.build_trie(patterns)
ac.build_automaton()
matches = ac.search(text)
print("Találatok:", matches)
Kimenet:
Találatok:
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <string>
using namespace std;
struct Node {
unordered_map<char, int> children;
int fail = 0;
vector<string> output;
};
class AhoCorasick {
vector<Node> trie;
public:
AhoCorasick() {
trie.emplace_back(); // Root node
}
void build_trie(const vector<string>& patterns) {
for (const string& pattern : patterns) {
int state = 0;
for (char c : pattern) {
if (!trie.children.count(c)) {
trie.children = trie.size();
trie.emplace_back();
}
state = trie.children;
}
trie.output.push_back(pattern);
}
}
void build_automaton() {
queue<int> q;
for (auto& : trie.children) {
trie.fail = 0;
q.push(value);
}
while (!q.empty()) {
int state = q.front();
q.pop();
for (auto& : trie.children) {
int fail = trie.fail;
while (fail != 0 && !trie.children.count(key)) {
fail = trie.fail;
}
trie.fail = trie.children.count(key) ? trie.children : 0;
trie.output.insert(
trie.output.end(),
trie.fail].output.begin(),
trie.fail].output.end()
);
q.push(next_state);
}
}
}
vector<pair<int, string>> search(const string& text) {
vector<pair<int, string>> matches;
int state = 0;
for (int i = 0; i < text.size(); ++i) {
char c = text;
while (state != 0 && !trie.children.count(c)) {
state = trie.fail;
}
state = trie.children.count(c) ? trie.children : 0;
for (const string& pattern : trie.output) {
matches.emplace_back(i - pattern.size() + 1, pattern);
}
}
return matches;
}
};
int main() {
vector<string> patterns = {"he", "she", "his", "hers"};
string text = "ushers";
AhoCorasick ac;
ac.build_trie(patterns);
ac.build_automaton();
auto matches = ac.search(text);
cout << "Találatok:" << endl;
for (auto& : matches) {
cout << "Pozíció: " << pos << ", Minta: " << pattern << endl;
}
return 0;
}
Kimenet:
Találatok: Pozíció: 1, Minta: he Pozíció: 1, Minta: she Pozíció: 2, Minta: hers
Az Aho-Corasick-algoritmus kiváló választás, ha nagy mennyiségű minta gyors keresésére van szükség egy szövegben, például kódvizsgálat, víruskeresés vagy nyelvi elemzés során.