AC 自动机(?
引子:(粘的概念
AC 自动机(Aho-Corasick 自动机)是一种用于字符串匹配的算法。它在一个文本中搜索所有可能的模式串,并支持多个模式串的同时匹配。AC 自动机通过构建一个有限状态自动机来实现高效的字符串匹配。
学了点java,打算实现一下,所以这是这个sb第一次用两个语言写分享
right,我们以一个简单的示例来演示 AC 自动机的基本概念和实现。
C++ code
我们将创建一个类来表示 AC 自动机,并实现其核心功能。
#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
class AhoCorasick {
private:
// 存储状态转移函数
std::unordered_map<std::string, std::unordered_map<char, int>> transitionFunction;
// 存储失败链接函数
std::unordered_map<int, std::vector<int>> failureFunction;
// 存储所有的模式串
std::vector<std::string> patterns;
// 初始状态
int initialState;
// 最后一个状态
int finalState;
void buildTransitionFunction() {
for (const std::string& pattern : patterns) {
int state = initialState;
for (char c : pattern) {
if (transitionFunction.find(pattern) == transitionFunction.end()) {
transitionFunction[pattern][c] = state;
} else {
transitionFunction[pattern][c] = transitionFunction[pattern][c];
}
state = transitionFunction[pattern][c];
}
// 添加终结状态到失败链接函数中
failureFunction[state].push_back(finalState);
}
}
void buildFailureFunction() {
std::queue<int> queue;
queue.push(initialState);
while (!queue.empty()) {
int state = queue.front();
queue.pop();
for (const std::string& pattern : patterns) {
for (const auto& pair : transitionFunction[pattern]) {
char c = pair.first;
int nextState = pair.second;
if (nextState == state) {
continue;
}
if (failureFunction.find(nextState) == failureFunction.end()) {
failureFunction[nextState] = {state};
} else {
failureFunction[nextState].push_back(state);
}
queue.push(nextState);
}
}
}
}
public:
AhoCorasick(const std::vector<std::string>& patterns) : patterns(patterns) {
// 初始化初始状态和终结状态
initialState = 0;
finalState = 1;
// 构建状态转移函数和失败链接函数
buildTransitionFunction();
buildFailureFunction();
}
void search(const std::string& text) {
int state = initialState;
for (char c : text) {
if (transitionFunction.find(text.substr(0, text.size() - 1)) != transitionFunction.end()) {
state = transitionFunction[text.substr(0, text.size() - 1)][c];
} else {
state = failureFunction[state][0];
}
}
// 输出匹配结果
for (int i = 0; i < state; i++) {
std::cout << patterns[i] << std::endl;
}
}
};
int main() {
std::vector<std::string> patterns = {"hello", "world", "python"};
AhoCorasick ac(patterns);
ac.search("helloworldpython");
return 0;
}
就这样(?
我们先定义了一个 AhoCorasick
类,这里面包含了状态转移函数 transitionFunction
、失败链接函数 failureFunction
、模式串列表 patterns
、初始状态 initialState
和终结状态 finalState
。
在构造函数中,我们首先初始化了初始状态和终结状态,然后构建了状态转移函数和失败链接函数。状态转移函数用于根据当前字符和已匹配的模式串来确定下一个状态,失败链接函数用于在没有匹配到任何模式串时跳转到可能匹配的状态。
在 search
方法中,我们根据输入的文本进行匹配。首先,我们将当前状态初始化为初始状态,然后逐个字符地遍历文本。如果当前字符在状态转移函数中存在对应的转移状态,我们就更新状态;否则,我们通过失败链接函数跳转到可能匹配的状态。最后,输出所有匹配到的模式串。
在 main
函数中,我们创建了一个 AhoCorasick
对象,并传入模式串列表进行构造。然后,我们调用 search
方法来搜索文本,并输出匹配结果。
好好好,那么如果你看懂了的话,下面的可以不看了qaq
Java 实现
个人尝试一下 Java 实现 AC 自动机。我们可以创建一个类来表示 AC 自动机。
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class AhoCorasick {
private Map<String, Map<Character, Integer>> transitionFunction;
private Map<Integer, List<Integer>> failureFunction;
private List<String> patterns;
private int initialState;
private int finalState;
public AhoCorasick(List<String> patterns) {
// 初始化初始状态和终结状态
initialState = 0;
finalState = 1;
// 构建状态转移函数和失败链接函数
transitionFunction = new HashMap<>();
failureFunction = new HashMap<>();
for (int i = 0; i < patterns.size(); i++) {
String pattern = patterns.get(i);
int state = initialState;
for (int j = 0; j < pattern.length(); j++) {
if (transitionFunction.containsKey(pattern.substring(0, j + 1))) {
state = transitionFunction.get(pattern.substring(0, j + 1)).get(pattern.charAt(j));
} else {
Map<Character, Integer> newMap = new HashMap<>();
newMap.put(pattern.charAt(j), state);
transitionFunction.put(pattern.substring(0, j + 1), newMap);
state = state;
}
}
// 添加终结状态到失败链接函数中
failureFunction.put(state, new ArrayList<>(Collections.singletonList(finalState)));
}
}
public void search(String text) {
int state = initialState;
for (char c : text.toCharArray()) {
if (transitionFunction.containsKey(text.substring(0, text.length() - 1))) {
state = transitionFunction.get(text.substring(0, text.length() - 1)).get(c);
} else {
state = failureFunction.get(state).get(0);
}
}
// 输出匹配结果
for (int i = 0; i < state; i++) {
System.out.println(patterns.get(i));
}
}
public static void main(String[] args) {
List<String> patterns = List.of("hello", "world", "python");
AhoCorasick ac = new AhoCorasick(patterns);
ac.search("helloworldpython");
}
}
我们首先定义了一个 AhoCorasick
类,它包含了状态转移函数 transitionFunction
、失败链接函数 failureFunction
、模式串列表 patterns
、初始状态 initialState
和终结状态 finalState
。
在构造函数中,我们首先初始化了初始状态和终结状态,然后构建了状态转移函数和失败链接函数。状态转移函数用于根据当前字符和已匹配的模式串来确定下一个状态,失败链接函数用于在没有匹配到任何模式串时跳转到可能匹配的状态。
在 search
方法中,我们根据输入的文本进行匹配。首先,我们将当前状态初始化为初始状态,然后逐个字符地遍历文本。如果当前字符在状态转移函数中存在对应的转移状态,我们就更新状态;否则,我们通过失败链接函数跳转到可能匹配的状态。最后,输出所有匹配到的模式串。
在 main
函数中,我们创建了一个 AhoCorasick
对象,并传入模式串列表进行构造。然后,我们调用 search
方法来搜索文本,并输出匹配结果。
换头像了(?
诶