昨天写了一个 AC 自动机的模版题，现在，我们需要基于这个模版，实现一个多模匹配的 map，具体是这样的，我们给一个 map<string, int>，然后给一个串，要求在这个串里面，把 map 中含有的 key 的 value 都返回出来。
注意到昨天的模版题的实现，是会去改动树本身的，同时也没有做一些内存管理方面的处理，另外的区别是昨天的题是考虑多个相同关键字的，而这个，由于 map 的 key 的唯一性，自然是不允许多个相同的 key 的，那么修改之后如下：
#include <iostream>
#include <stdio.h>
#include <memory.h>
#include <string>
#include <queue>
#include <set>
#define CHAR_COUNT 128
class Node {
public:
Node() {
memset(this, 0, sizeof(*this));
}
char ch;
Node* fail;
Node* next[CHAR_COUNT];
bool end;
int value;
};
class Trie {
public:
Node* root;
Trie() {
root = new Node();
}
~Trie() {
clear(root);
}
void insert(const char* strKey, int value) {
Node* p = root;
for (int i = 0; strKey[i]; i++) {
char ch = strKey[i];
if (p->next[ch] == NULL) {
p->next[ch] = new Node();
}
p = p->next[ch];
p->ch = strKey[i];
}
p->end = true;
p->value = value;
}
void build() {
std::queue<Node*> q;
q.push(root);
while ( ! q.empty()) {
Node* tmp = q.front();
q.pop();
for (int i = 0; i < CHAR_COUNT; i++) {
if (tmp->next[i]) {
if (tmp == root) {
tmp->next[i]->fail = root;
} else {
Node* p = tmp->fail;
while (p) {
if (p->next[i]) {
tmp->next[i]->fail = p->next[i];
break;
}
p = p->fail;
}
if ( ! p) {
tmp->next[i]->fail = root;
}
}
q.push(tmp->next[i]);
}
}
}
}
std::vector<int> query(const char* str) {
std::vector<int> result;
Node* p = root;
for (int i = 0; str[i]; i++) {
char ch = str[i];
while ( ! p->next[ch] && p != root) {
p = p->fail;
}
p = p->next[ch];
if ( ! p) {
p = root;
}
Node* tmp = p;
while (tmp != root) {
if (tmp->end) {
result.push_back(tmp->value);
}
tmp = tmp->fail;
}
}
return result;
}
void clear(Node*& p) {
if (p) {
for (int i = 0; i < CHAR_COUNT; i++) {
clear(p->next[i]);
}
delete p;
p = NULL;
}
}
};
int main() {
int t;
scanf("%d", &t);
while (t--) {
Trie trie;
int n;
scanf("%d", &n);
while (n--) {
std::string keyword;
int value;
std::cin>>keyword>>value;
trie.insert(keyword.c_str(), value);
}
trie.build();
std::string query;
std::cin>>query;
std::vector<int> result = trie.query(query.c_str());
printf("size %d\n", result.size());
for (std::vector<int>::iterator it = result.begin(); it != result.end(); it++) {
printf("%d\n", *it);
}
}
return 0;
}
对于这个实现，思路上应该是没有问题，但是，看一下下面这个测试用例。
1 2 11 11 111 111 111
他的输出却是这个样子的
size 3 11 111 11
嗯，11 这个 value 出现了两次。
让我们来分析一下，模拟程序的运行过程，看看是什么情况。
首先给出失败指针的结果图如上，我们来看看这个失败指针是怎么得出来的。
- 第 50 行，把 root 节点加入队列（root 节点的失败指针是 NULL），然后进入 51 行开始的队列处理循环
- 取出 root 节点，根据 56 – 58 行，对 root 节点的所有直接子节点，将其失败指针指向 root，对应图上的失败指针 1。同时 71 行将 root 节点的所有子节点追加入队列。至此，队列中有一个节点，也就是第一个 a 节点。
- 回到 52 行，取出第一个 a 节点，开始处理。注意到在 54 – 73 行的 for 循环中，tmp 指针是一直不会发生变化的，所以，这个 tmp 指针，可以理解成“当前父节点”，而在此轮循环中，任务就是为这个“当前父节点”的全部非空子节点找好失败指针。那么，对于第一个 a 节点，代码走到 59 行，指针 p 指向第一个 a 节点的失败指针，也就是 root，然后进入 60 – 66 的 while 循环。由于 root 节点有一个字符为 a 的子节点，于是在第一轮的循环中，就为第二个 a 节点找好了失败指针，也就是让第二个 a 节点的失败指针指向第一个 a 节点。
- 第二个 a 节点成为“当前父节点”，同理，为其子节点（也就是第三个 a 节点）找到的失败指针指向了第二个 a 节点。至此所有失败指针建立完成。
回到 60 – 66 行这个 while 循环，为什么这个循环就能可以建立出正确的失败指针呢。这个 while 循环的原理是：一级一级的沿着失败指针回溯，直到某一个节点的包含有跟“当前父节点”相同字符的子节点（61 行）并把“当前父节点”的对应子节点的失败指针指向这个找到的子节点（62 行）并跳出循环（63 行）或者一直找到空节点（65 行）为止。
那么，这样一来，就可以保证，为“当前父节点”的所有子节点找到的失败指针，指向的节点的字符，都是跟这个子节点一样的，而父节点的失败指针，也在上一轮的 BFS 遍历中，指向了一个跟父节点含有相同字符（或者）跟节点的指针，那么，递归的，就可以保证，从那个找到的失败指针往上走，关键词的字符顺序是跟当前路径下来的字符顺序是能匹配（后缀是匹配的）的，所以，失败指针就能据此正确的建立起来。
然后让我们来看一下查询的过程：
- 对于第一个字母，走到第一个 a 节点，沿着失败指针找，找到 root，跳出
- 对于第二个字母，走到第二个 a 节点，然后他的 end 标志是 true 的，于是把这个节点的 value 值 11 加入结果集，沿着失败指针，找到第一个 a 节点，再沿着失败指针，找到 root 节点，跳出
- 对于第三个字母，走到第三个 a 节点，并发现第三个 a 节点的 end 标志是 true，于是把这个节点的 value 值 111 加入结果集，并继续沿着失败指针，找到第二个 a 节点，发现他是 end 的，于是将 11 加入结果集，再沿着失败指针，找到第一个 a 节点和 root 节点，跳出。
注意到悲剧就在第三步的“沿着失败指针回溯”这个环节上，再回到的了第二个 a 节点那里，昨天那个版本之所以不存在这个问题，是因为他在每次加入之后，都把那个节点的 prefix 置为了 -1 并且在循环的时候检查这个 prefix，但是这样就污染了树的内容，从而不利于多次查询。
那么为什么他这里需要沿着失败指针一直回溯呢？回想到之前建立失败指针的过程，由于一个节点下面，失败指针只有一个，这个指针将会指向第一个被找到的具有相同后缀的节点上，但是，无法排除还有其他相同后缀的节点，而这些节点要怎么去关联起来呢，就靠那个被指向的失败节点的失败指针继续往后了，有点链表的感觉，所以，在查询的时候，也需要沿着这些失败指针，一直回溯，直到找到 root 节点为止。
至此基本上就明白了，至于解决方法，我想到的办法也很简单，其实就是在 end 节点上保存这个 key 的 string，然后查询的时候用一个 map 来存放中间结果就可以了。
修改之后的代码也放一份吧：
#include <iostream>
#include <stdio.h>
#include <memory.h>
#include <string>
#include <queue>
#include <map>
#include <set>
#define CHAR_COUNT 128
class Node {
public:
Node() {
ch = 0;
fail = NULL;
memset(next, NULL, sizeof(next));
end = false;
key = "";
value = 0;
}
char ch;
Node* fail;
Node* next[CHAR_COUNT];
bool end;
std::string key;
int value;
};
class Trie {
public:
Node* root;
Trie() {
root = new Node();
}
~Trie() {
clear(root);
}
void insert(const char* strKey, int value) {
Node* p = root;
for (int i = 0; strKey[i]; i++) {
char ch = strKey[i];
if (p->next[ch] == NULL) {
p->next[ch] = new Node();
}
p = p->next[ch];
p->ch = strKey[i];
}
p->end = true;
p->key.assign(strKey);
p->value = value;
}
void build() {
std::queue<Node*> q;
q.push(root);
while ( ! q.empty()) {
Node* tmp = q.front();
q.pop();
for (int i = 0; i < CHAR_COUNT; i++) {
if (tmp->next[i]) {
if (tmp == root) {
tmp->next[i]->fail = root;
} else {
Node* p = tmp->fail;
while (p) {
if (p->next[i]) {
tmp->next[i]->fail = p->next[i];
break;
}
p = p->fail;
}
if ( ! p) {
tmp->next[i]->fail = root;
}
}
q.push(tmp->next[i]);
}
}
}
}
std::map<std::string, int> query(const char* str) {
std::map<std::string, int> result;
Node* p = root;
for (int i = 0; str[i]; i++) {
char ch = str[i];
while ( ! p->next[ch] && p != root) {
p = p->fail;
}
p = p->next[ch];
if ( ! p) {
p = root;
}
Node* tmp = p;
while (tmp != root) {
if (tmp->end) {
result[tmp->key] = tmp->value;
}
tmp = tmp->fail;
}
}
return result;
}
void clear(Node*& p) {
if (p) {
for (int i = 0; i < CHAR_COUNT; i++) {
clear(p->next[i]);
}
delete p;
p = NULL;
}
}
};
int main() {
int t;
scanf("%d", &t);
while (t--) {
Trie trie;
int n;
scanf("%d", &n);
while (n--) {
std::string keyword;
int value;
std::cin>>keyword>>value;
trie.insert(keyword.c_str(), value);
}
trie.build();
std::string query;
std::cin>>query;
std::map<std::string, int> result = trie.query(query.c_str());
printf("size %d\n", result.size());
for (std::map<std::string, int>::iterator it = result.begin(); it != result.end(); it++) {
printf("%s -> %d\n", it->first.c_str(), it->second);
}
}
return 0;
}
稍微注意一下，由于结构体里面有了 stl 容器 string，所以不能再用 memset 来初始化整个结构体了。
虽不明但觉厉…
其实这个还是很有应用价值的，例如说，发微博，或者留言的时候，需要敏感词过滤，敏感词可能有成千上万个，一条留言大约两三百个字符，你总不能循环的调用成千上万次的 str find 函数吧，这个时候就要靠这个 ac 自动机了
这个就是那个论文的东西？
啥论文。。怎么会扯到论文去了