forked from dairongpeng/algorithm-note
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy path24.md
More file actions
169 lines (131 loc) · 4.56 KB
/
24.md
File metadata and controls
169 lines (131 loc) · 4.56 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
- [1 AC自动机](#1)
* [1.1 AC自动机的实现](#11)
<h1 id='1'>1 AC自动机</h1>
KMP算法解决的问题是，在一个大字符串中，求目标match串存在还是不存在，最早存在的地方在哪
AC自动机要解决的问题是，在一个文章中，有一些候选字符串，求这个文章中命中了哪些候选串。
<h2 id='11'>1.1 AC自动机的实现</h2>
为每一个候选串建立一个前缀树，每个树节点都有一个fail指针。头节点fail指针人为规定指向null，第一层节点的fail指针人为规定，指向头节点。建立好前缀树后，宽度优先遍历设置全部的fail指针
> 比较绕，看不懂看代码
宽度优先遍历设置fali的指针的过程，如果某个节点的指针指向null,孩子的fail指针指向当前的父亲；如果某个节点的fail指针指向不为空的节点A,A孩子的路径为B,那么A的fali指针有没有指向B的路径，如果有，A孩子的fail指针，指向父亲节点的fail指针指向的B；如果父亲没有指向B的路，再找fail直到为null后，孩子fail指针指向头结点
```Java
package class08;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
public class Code01_AC {
// 前缀树的节点
public static class Node {
// 如果一个node，end为空，不是结尾
// 如果end不为空，表示这个点是某个字符串的结尾，end的值就是这个字符串
public String end;
// 只有在上面的end变量不为空的时候，endUse才有意义
// 表示，这个字符串之前有没有加入过答案
public boolean endUse;
public Node fail;
public Node[] nexts;
public Node() {
endUse = false;
end = null;
fail = null;
// 假设前缀树的节点上的值只是小写字母，有26个指向。经典前缀树
nexts = new Node[26];
}
}
// AC自动机
public static class ACAutomation {
private Node root;
// 建头结点
public ACAutomation() {
root = new Node();
}
// 先建前缀树，建好之后再build所有节点的fail指针
public void insert(String s) {
char[] str = s.toCharArray();
Node cur = root;
int index = 0;
for (int i = 0; i < str.length; i++) {
index = str[i] - 'a';
if (cur.nexts[index] == null) {
Node next = new Node();
cur.nexts[index] = next;
}
cur = cur.nexts[index];
}
cur.end = s;
}
// 建立所有节点的fail指针
public void build() {
Queue<Node> queue = new LinkedList<>();
queue.add(root);
Node cur = null;
Node cfail = null;
while (!queue.isEmpty()) {
// 当前节点弹出，
// 当前节点的所有后代加入到队列里去，
// 当前节点给它的子去设置fail指针
// cur -> 父亲
cur = queue.poll();
for (int i = 0; i < 26; i++) { // 所有的路
if (cur.nexts[i] != null) { // 找到所有有效的路
cur.nexts[i].fail = root; //
cfail = cur.fail;
while (cfail != null) {
if (cfail.nexts[i] != null) {
cur.nexts[i].fail = cfail.nexts[i];
break;
}
cfail = cfail.fail;
}
queue.add(cur.nexts[i]);
}
}
}
}
// build好之后，可以查文章有哪些候选串
public List<String> containWords(String content) {
char[] str = content.toCharArray();
Node cur = root;
Node follow = null;
int index = 0;
List<String> ans = new ArrayList<>();
for (int i = 0; i < str.length; i++) {
index = str[i] - 'a'; // 路
// 如果当前字符在这条路上没配出来，就随着fail方向走向下条路径
while (cur.nexts[index] == null && cur != root) {
cur = cur.fail;
}
// 1) 现在来到的路径，是可以继续匹配的
// 2) 现在来到的节点，就是前缀树的根节点
cur = cur.nexts[index] != null ? cur.nexts[index] : root;
follow = cur;
while (follow != root) {
if(follow.endUse) {
break;
}
// 不同的需求，在这一段之间修改
if (follow.end != null) {
ans.add(follow.end);
follow.endUse = true;
}
// 不同的需求，在这一段之间修改
follow = follow.fail;
}
}
return ans;
}
}
public static void main(String[] args) {
ACAutomation ac = new ACAutomation();
ac.insert("dhe");
ac.insert("he");
ac.insert("abcdheks");
// 设置fail指针
ac.build();
List<String> contains = ac.containWords("abcdhekskdjfafhasldkflskdjhwqaeruv");
for (String word : contains) {
System.out.println(word);
}
}
}
```