-
Notifications
You must be signed in to change notification settings - Fork 0
/
hdoj2222.cpp
158 lines (129 loc) · 4.53 KB
/
hdoj2222.cpp
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
// Created by zhu on 2018/1/23.
//
#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include <queue>
#include <fstream>
using namespace std;
struct Node {
int cnt;//是否为该单词的最后一个结点
Node *fail;//失败指针
Node *next[26];//Trie中每个结点的各个节点
};
void init(Node *root);
void buildTrie(char *keyword);
void buildAcAutomation(Node *root);
int query(Node *root);
Node *Queue[500005];//队列,方便用BFS构造失败指针
char s[1000005];//主字符串
char keyword[55];//需要查找的单词
Node *root;//头结点
int main() {
int T;
int N;
ifstream is("data.dat");
is >> T;
while (T--) {
root = new Node;
init(root);
is >> N;
for (int i = 0; i < N; i++) {
is >> keyword;
buildTrie(keyword);
}
buildAcAutomation(root);
is >> s;
cout << query(root) << endl;
}
return 0;
}
void init(Node *root) {//每个结点的初始化
root->cnt = 0;
root->fail = nullptr;
for (int i = 0; i < 26; i++) {
root->next[i] = nullptr;
}
}
void buildTrie(char *keyword) {//构建Trie树
Node *cur, *next;
int i, nextWord;
int len = strlen(keyword);
for (i = 0, cur = root; i < len; i++) {
nextWord = keyword[i] - 'a';
if (cur->next[nextWord] == nullptr) {
next = (struct Node *) malloc(sizeof(Node));
init(next);
cur->next[nextWord] = next;//结点链接
}
cur = cur->next[nextWord];//指针移动到下一个结点
}
cur->cnt++;//单词最后一个结点cnt++,代表一个单词
}
void buildAcAutomation(Node *root) {
int uBound = 0, lBound = 0;//队列头、尾指针
Queue[uBound++] = root;//先将root入队
while (uBound != lBound) {
Node *reBackPtr = nullptr;
Node *cur = Queue[lBound++];//弹出队头结点
for (int i = 0; i < 26; i++) {
if (cur->next[i] != nullptr) {//找到实际存在的字符结点
//cur->next[i] 为该结点,temp为其父结点
if (cur == root) {//若是第一层中的字符结点,则把该结点的失败指针指向root
cur->next[i]->fail = root;
} else {//依次回溯该节点的父节点的失败指针直到某节点的next[i]与该节点相同,
//则把该节点的失败指针指向该next[i]节点;
//若回溯到 root 都没有找到,则该节点的失败指针指向 root
reBackPtr = cur->fail;//将该结点的父结点的失败指针给p
while (reBackPtr != nullptr) {
if (reBackPtr->next[i] != nullptr) {
cur->next[i]->fail = reBackPtr->next[i];
break;
}
reBackPtr = reBackPtr->fail;
}
//让该结点的失败指针也指向root
if (reBackPtr == nullptr) {
cur->next[i]->fail = root;
}
}
Queue[uBound++] = cur->next[i];//每处理一个结点,都让该结点的所有孩子依次入队
}
}
}
}
int query(Node *root) { //i为主串指针,p为模式串指针
int i, ch, count = 0;
Node *cur = root;
int len = strlen(s);
for (i = 0; i < len; i++) {
ch = s[i] - 'a';
//由失败指针回溯查找,判断s[i]是否存在于Trie树中
while (cur->next[ch] == nullptr && cur != root) {
cur = cur->fail;
}
//cur->next[ch]!=nullptr;
cur = cur->next[ch];//找到后p指针指向该结点
if (cur == nullptr) {//若指针返回为空,则没有找到与之匹配的字符
cur = root;
}
Node *temp = cur;//匹配该结点后,沿其失败指针回溯,判断其它结点是否匹配
while (temp != root)//匹配结束控制
{
if (temp->cnt >= 0)//判断该结点是否被访问
{
count += temp->cnt;//由于cnt初始化为 0,所以只有cnt>0时才统计了单词的个数
temp->cnt = -1;//标记已访问过
} else {//结点已访问,退出循环
break;
}
temp = temp->fail;//回溯 失败指针 继续寻找下一个满足条件的结点
}
}
return count;
}