-
Notifications
You must be signed in to change notification settings - Fork 2
/
ACAutoMata.java
135 lines (114 loc) · 3.93 KB
/
ACAutoMata.java
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
package homework.string;
import java.util.*;
public class ACAutoMata {
private ACNode root;
public ACAutoMata() {
this.root = new ACNode("/");
}
private void insert (String pattern) {
ACNode node = this.root;
int len = pattern.length();
for (int i = 0; i < len; i++) {
String c = pattern.charAt(i) + "";
if(Objects.isNull(node.children.get(c))) {
node.children.put(c, new ACNode(c));
}
node = node.children.get(c);
}
node.isEndingChar = true;
node.length = pattern.length();
}
private void buildFailurePointer() {
ACNode root = this.root;
LinkedList<ACNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
ACNode p = queue.pop();
for(ACNode pc: p.children.values()){
if (Objects.isNull(pc)) {
continue;
}
if(p == root) {
pc.fail = root;
} else {
ACNode q = p.fail;
while (Objects.nonNull(q)) {
ACNode qc = q.children.get(pc.data);
if(Objects.nonNull(qc)) {
pc.fail = qc;
break;
}
q = q.fail;
}
if(Objects.isNull(q)) {
pc.fail = root;
}
}
queue.add(pc);
}
}
}
/**
* 返回匹配的所有字符串。如果不匹配则返回为空list。
* @param text
* @return
*/
private List<String> match (String text) {
ACNode root = this.root;
ACNode p = root;
int n = text.length();
List<String> matchedList = new ArrayList<String>();
for(int i = 0; i < n; i++) {
String c = text.charAt(i) + "";
while(Objects.isNull(p.children.get(c)) && p != root){
p = p.fail;
}
p = p.children.get(c);
if(Objects.isNull(p)) {
p = root;
}
ACNode tmp = p;
while ( tmp != root) {
if (tmp.isEndingChar == true) {
//System.out.println("Start from " + (i - p.length + 1)+" "+p.length);
int start = i - p.length + 1;
matchedList.add(text.substring(start,start+p.length));
p = root;
break;
}
tmp = tmp.fail;
}
}
return matchedList;
}
public static List<String> match(String text, String[] patterns) {
ACAutoMata automata = new ACAutoMata();
for (String pattern: patterns) {
automata.insert(pattern);
}
automata.buildFailurePointer();
return automata.match(text);
}
public class ACNode {
private String data;
private Map<String, ACNode> children;
private Boolean isEndingChar;
private Integer length;
private ACNode fail;
public ACNode(String data) {
this.data = data;
this.children = new HashMap<>();
this.isEndingChar = false;
this.length = 0;
this.fail = null;
}
}
public static void main(String[] args) {
String[] patterns = {"at", "art", "oars", "soar"};
String text = "soarsoars";
System.out.println(match(text, patterns));
String[] patterns2 = {"Fxtec Pro1", "谷歌Pixel"};
String text2 = "一家总部位于伦敦的公司Fxtex在MWC上就推出了一款名为Fxtec Pro1的手机,该机最大的亮点就是采用了侧滑式全键盘设计。DxOMark年度总榜发布 华为P20 Pro/谷歌Pixel 3争冠";
System.out.println(match(text2, patterns2));
}
}