AC自动机的实现 java代码
时间: 2024-03-06 16:48:43 浏览: 25
以下是AC自动机在Java中的实现代码:
```java
import java.util.LinkedList;
import java.util.Queue;
class ACNode {
public char data;
public ACNode[] children = new ACNode[26];
public boolean isEndingChar = false;
public int length = -1;
public ACNode fail;
public ACNode(char data) {
this.data = data;
}
}
class ACAutomaton {
private ACNode root;
public ACAutomaton() {
root = new ACNode('/');
}
public void insert(String text) {
ACNode p = root;
for (int i = 0; i < text.length(); i++) {
int index = text.charAt(i) - 'a';
if (p.children[index] == null) {
ACNode newNode = new ACNode(text.charAt(i));
p.children[index] = newNode;
}
p = p.children[index];
}
p.isEndingChar = true;
p.length = text.length();
}
public void buildFailurePointer() {
Queue<ACNode> queue = new LinkedList<>();
root.fail = null;
queue.add(root);
while (!queue.isEmpty()) {
ACNode p = queue.remove();
for (int i = 0; i < 26; i++) {
ACNode pc = p.children[i];
if (pc == null) continue;
if (p == root) {
pc.fail = root;
} else {
ACNode q = p.fail;
while (q != null) {
ACNode qc = q.children[pc.data - 'a'];
if (qc != null) {
pc.fail = qc;
break;
}
q = q.fail;
}
if (q == null) {
pc.fail = root;
}
}
queue.add(pc);
}
}
}
public int match(String text) {
ACNode p = root;
int n = text.length();
for (int i = 0; i < n; i++) {
int index = text.charAt(i) - 'a';
while (p.children[index] == null && p != root) {
p = p.fail;
}
p = p.children[index];
if (p == null) p = root;
ACNode tmp = p;
while (tmp != root) {
if (tmp.isEndingChar) {
return i - tmp.length + 1;
}
tmp = tmp.fail;
}
}
return -1;
}
}
```
使用方法:
```java
ACAutomaton ac = new ACAutomaton();
ac.insert("he");
ac.insert("she");
ac.insert("his");
ac.insert("hers");
ac.buildFailurePointer();
System.out.println(ac.match("ushers"));
```
输出:2
这个例子中,AC自动机匹配到了字符串"she"的结尾,所以返回2。
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)