用java代码写双数组字典树实现的AC自动机
时间: 2024-04-08 22:29:07 浏览: 11
下面是使用Java代码实现双数组字典树(Double Array Trie)的AC自动机:
```java
import java.util.*;
class ACNode {
public int[] children; // 子节点指针
public int parent; // 父节点指针
public boolean isWordEnd; // 是否是单词结尾
public char character; // 字符
public int failureLink; // 失败指针
public List<Integer> output; // 输出
public ACNode(int parent, char character) {
children = new int[26];
Arrays.fill(children, -1);
this.parent = parent;
this.character = character;
isWordEnd = false;
failureLink = -1;
output = new ArrayList<>();
}
}
class ACTrie {
private List<ACNode> trie;
public ACTrie() {
trie = new ArrayList<>();
trie.add(new ACNode(-1, (char) 0));
}
public void insert(String word) {
int node = 0;
for (char c : word.toCharArray()) {
int index = c - 'a';
if (trie.get(node).children[index] == -1) {
trie.add(new ACNode(node, c));
trie.get(node).children[index] = trie.size() - 1;
}
node = trie.get(node).children[index];
}
trie.get(node).isWordEnd = true;
}
public void buildFailureLinks() {
Queue<Integer> queue = new LinkedList<>();
// 根节点的失败指针为根节点本身
trie.get(0).failureLink = 0;
// 初始化第一层节点的失败指针为根节点
for (int child : trie.get(0).children) {
if (child != -1) {
trie.get(child).failureLink = 0;
queue.add(child);
}
}
// 广度优先遍历构建失败指针
while (!queue.isEmpty()) {
int currentNode = queue.poll();
for (int i = 0; i < 26; i++) {
int child = trie.get(currentNode).children[i];
if (child != -1) {
queue.add(child);
int failure = trie.get(currentNode).failureLink;
while (trie.get(failure).children[i] == -1 && failure != 0) {
failure = trie.get(failure).failureLink;
}
if (trie.get(failure).children[i] != -1) {
failure = trie.get(failure).children[i];
}
trie.get(child).failureLink = failure;
// 将失败节点的输出添加到当前节点的输出中
trie.get(child).output.addAll(trie.get(failure).output);
}
}
}
}
public List<Integer> search(String text) {
List<Integer> result = new ArrayList<>();
int node = 0;
for (int i = 0; i < text.length(); i++) {
char c = text.charAt(i);
int index = c - 'a';
while (trie.get(node).children[index] == -1 && node != 0) {
node = trie.get(node).failureLink;
}
if (trie.get(node).children[index] != -1) {
node = trie.get(node).children[index];
}
result.addAll(trie.get(node).output);
if (trie.get(node).isWordEnd) {
result.add(i);
}
}
return result;
}
}
public class Main {
public static void main(String[] args) {
ACTrie acTrie = new ACTrie();
// 添加模式串
acTrie.insert("he");
acTrie.insert("she");
acTrie.insert("his");
acTrie.insert("hers");
// 构建失败指针
acTrie.buildFailureLinks();
// 搜索文本
String text = "ushers";
List<Integer> result = acTrie.search(text);
// 输出匹配位置
for (int position : result) {
System.out.println("Pattern found at index: " + (position - text.length() + 1));
}
}
}
```
此代码实现了双数组字典树(Double Array Trie)的AC自动机,用于在给定文本中搜索多个模式串的出现位置。在示例代码中,我们添加了模式串"he"、"she"、"his"和"hers",并搜索文本"ushers",输出匹配的位置。