从 KMP 到 AC 自动机：单串匹配、Trie 与多模匹配
Trie 树
Trie 树一般指字典树，又称单词查找树，是一种树形结构，是一种哈希树的变种。
典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。
它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
//(POJ 3630) http://poj.org/problem?id=3630
/*
题目描述：给定 T 组数据，判断每组数据是否有存在前缀，有-NO，无-YES
解法：Trie树，参考 "字典树统计前缀1"
*/
int T, n, tot;
int ch[100005][10];
bool bo[100005];
char s[20];
void clean()
{
memset(ch, 0, sizeof(ch));
memset(bo, 0, sizeof(bo));
return;
}
bool add(char *s)
{
int len = strlen(s);
int u = 1;
bool flag = false;
for (int i = 0; i < len; i++)
{
int c = s[i] - '0';
if (!ch[u][c])
ch[u][c] = ++tot;
else if (i == len - 1) // 如果为当前字符串末尾，但该结点还有其他数据
flag = true;
u = ch[u][c];
if (bo[u])
flag = true;
}
bo[u] = true;
return flag;
}
int main()
{
bool ans;
scanf("%d", &T);
while (T--)
{
ans = false;
scanf("%d", &n);
tot = 1;
clean(); // 初始化
for (int i = 1; i <= n; i++)
{
scanf("%s", s);
if (add(s))
ans = true;
}
if (ans == true)
printf("NO\n");
else
printf("YES\n");
}
return 0;
}#include <cstdio>
#include <cstring>
using namespace std;
/*
题目描述：给定n个字符串，并给出m个询问，回答含有询问中的字符串个数
解法：Trie树每个节点存放符合要求的字符串个数
（和 1 的很像）
*/
struct node
{
int s, v[27]; // s存放当前节点前缀的符合要求的字符串个数，v存放叶子结点位置
node() // 无参构造函数，用于进行初始化
{
s = 0;
memset(v, -1, sizeof(v));
}
} t[410000]; // 定义叶子结点
int tot = 1;
char a[100];
void bt(int root)
{
int x = root;
int len = strlen(a + 1);
for (int i = 1; i <= len; ++i)
{
int y = a[i] - 'a' + 1;
if (t[x].v[y] == -1)
t[x].v[y] = ++tot;
x = t[x].v[y];
t[x].s++;
}
}
int find(int root)
{
int x = root;
int len = strlen(a + 1);
for (int i = 1; i <= len; ++i)
{
int y = a[i] - 'a' + 1;
if (t[x].v[y] == -1)
return 0;
x = t[x].v[y];
}
return t[x].s;
}
int main()
{
int n, m;
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
{
scanf("%s", a + 1);
bt(1);
}
scanf("%d", &m);
for (int i = 1; i <= m; ++i)
{
scanf("%s", a + 1);
printf("%d\n", find(1));
}
return 0;
}#include <cstdio>
#include <cstring>
using namespace std;
/*
题目描述：给定n个字符串，并给出m个询问，回答含有询问中的字符串个数
解法：Trie树每个节点存放符合要求的字符串个数
*/
int ch[410000][27]; // 存放 Trie 树
int tot = 1; // 记录 Trie树的大小
int s[410000]; // 记录该结点前缀的字符串个数
char a[100];
void bt(int root)
{
int u = root;
int len = strlen(a + 1);
for (int i = 1; i <= len; ++i)
{
int c = a[i] - 'a' + 1; // 1-a 2-b ...
if (!ch[u][c]) // 如果没有该叶子结点
ch[u][c] = ++tot; // 在当前节点加入子节点的编号
u = ch[u][c]; // 将子节点设为当前节点
s[u]++; // 子节点的数值加一，用于记录该前缀的字符串个数
}
}
int find(int root)
{
int u = root;
int len = strlen(a + 1);
for (int i = 1; i <= len; ++i)
{
int c = a[i] - 'a' + 1;
if (!ch[u][c]) // 不存在叶子结点
return 0;
u = ch[u][c]; // 将叶子结点记为当前结点
}
return s[u]; // 返回个数
}
int main()
{
int n, m;
scanf("%d", &n); // 共n个字符串
for (int i = 1; i <= n; ++i)
{
scanf("%s", a + 1); // 每个字符串从a[1]开始哦
bt(1); // 存进去
}
scanf("%d", &m);
for (int i = 1; i <= m; ++i)
{
scanf("%s", a + 1);
printf("%d\n", find(1));
}
return 0;
}KMP
KMP 算法是一种改进的字符串匹配算法。
KMP 算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。
具体实现就是通过一个 next() 函数实现，函数本身包含了模式串的局部匹配信息。
KMP 算法的时间复杂度 O(m+n) 。
详见代码：
#include <cstdio>
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdlib>
using namespace std;
//(Hdu 2087) http://acm.hdu.edu.cn/showproblem.php?pid=2087
/*
题目描述：给定两个字符串 A、B ，求 A 中有多少个 B 的子串（不可重叠）
解法：KMP（详见txt文档）
*/
char A[1007], B[1007];
int P[1007]; // P 数组就是 next 数组。
int n, m;
void pre() // 求 P 数组（即 next 数组）
{
P[1] = 0; // 记得本题中字符串从 1 开始
int j = 0;
for (int i = 1; i < m; i++)
{
while (j > 0 && B[j + 1] != B[i + 1])
j = P[j];
if (B[j + 1] == B[i + 1])
j++;
P[i + 1] = j;
}
}
int kmp()
{
int ans = 0, j = 0;
for (int i = 0; i < n; i++)
{
while (j > 0 && B[j + 1] != A[i + 1])
j = P[j];
if (B[j + 1] == A[i + 1])
j++;
if (j == m)
{
ans++;
j = 0;
}
}
return ans;
}
int main()
{
while (cin >> A + 1)
{
if (A[1] == '#')
break;
scanf("%s", B + 1);
m = strlen(B + 1);
n = strlen(A + 1);
pre();
printf("%d\n", kmp());
}
return 0;
}核心代码：
void pre() // 求 P 数组（即 next 数组）
{
P[1] = 0; // 记得本题中字符串从 1 开始
int j = 0;
for (int i = 1; i < m; i++)
{
while (j > 0 && B[j + 1] != B[i + 1])
j = P[j];
if (B[j + 1] == B[i + 1])
j++;
P[i + 1] = j;
}
}一、KMP 算法
目的：找到模式串 B 在原字符串 A 中 第一次出现的位置。
n、m 分别为 A 和 B 的长度
流程：
[STEP 1]
if A[i+1]==B[j+1]
i++,j++;
i
A: ababcabcacbab
B: abcac
j[STEP 2]
if A[i+1]==B[j+1]
i++,j++;
i
A: ababcabcacbab
B: abcac
j[STEP 3]
if A[i+1]!=B[j+1]
j=next[j];
i
A: ababcabcacbab
B: abcac
j
if A[i+1]==B[j+1]（如果不等于的话就只加i）
i++,j++;
i
A: ababcabcacbab
B: abcac
j[STEP 4]
略二、next 数组的求法
next 数组记录最长相同前缀后缀
具体来说，就是 next 数组负责记录 B 字符串（也就是待查找子串）每个位置的属性，next[i] 记录 B[0…i] 中的前缀和后缀最长有多少一样的，比如 abcdab 中，[ab]cde[ab] 最长相同前缀后缀为 ab。
例：
a next[0]=0（注意！这是默认值 0 ，不是 1 ）
ab next[1]=0（a!=b）
abc next[2]=0（a!=c）
abca next[3]=1（a==a）
abcab next[4]=2（ab==ab）
abcabc next[5]=3（abc==abc）next 数组的操作与 KMP 类似
例：abcaba
初始状态
0
i
B: abcaba
jif B[j+1]!=B[i+1]
i++;
00
i
B: abcaba
jif B[j+1]!=B[i+1]
i++;
000
i
B: abcaba
jif B[j+1]==B[i+1]
i++,j++;
0001
i
B: abcaba
jif B[j+1]==B[i+1]
i++,j++;
00012
i
B: abcaba
jif B[j+1]!=B[i+1]
j=next[j];
if B[j+1]==B[i+1]
i++,j++;
000121
i
B: abcaba
j注：部分资料来源于百度百科
AC 自动机
Aho-Corasick automaton，是著名的多模匹配算法。
一个常见的例子就是给出 n 个单词，再给出一段包含 m 个字符的文章，让你找出有多少个单词在文章里出现过。
AC 自动机就是 Trie 树上的 KMP。
详见代码：
#include <cstdio>
#include <cstring>
using namespace std;
/*
题目描述：给定 n 个单词，求这 n 个单词出现在文章 S 中的个数（不重复计算）。
解法：AC自动机（Trie树上的KMP）
*/
int ans, cnt;
int ch[500005][26], bo[500005]; // ch 存放 Trie 树，bo 存放单词末尾标记
int nxt[500005]; // 失配指针，有时也写作 fail[]
int que[500005]; // 也就是 BFS 的 h 数组
void make(char *s) // 将字符串 s 存入 Trie 树中。
{
int u = 1, len = strlen(s);
for (int i = 0; i < len; ++i)
{
int c = s[i] - 'a';
if (!ch[u][c])
{
ch[u][c] = ++cnt;
memset(ch[cnt], 0, sizeof(ch[cnt]));
}
u = ch[u][c];
}
bo[u]++;
return;
}
void bfs()
{
for (int i = 0; i <= 25; ++i)
ch[0][i] = 1; // 0 结点的每一个字符都指向 root 结点（初始化）
que[1] = 1;
nxt[1] = 0; // 构建 nxt 数组，root 默认指向 0 结点
for (int q1 = 1, q2 = 1; q1 <= q2; ++q1) // BFS
{
int u = que[q1];
for (int i = 0; i <= 25; ++i)
{
if (!ch[u][i]) // 如果到叶子结点的话则通过 nxt 往回跳
ch[u][i] = ch[nxt[u]][i];
else
{
que[++q2] = ch[u][i];
int v = nxt[u];
// 符合条件的 v ：查找父亲的前缀指针(nxt)指向的节点，通过 nxt 一直跳，
// 直到找到该结点的有通过 i 连接的儿子
while (v > 0 && !ch[v][i]) // 通过 nxt 一直跳直到找到符合的
v = nxt[v];
nxt[ch[u][i]] = ch[v][i]; // nxt 的跳转
}
}
}
}
void find(char *s)
{
int u = 1, len = strlen(s), c, k;
for (int i = 0; i < len; ++i)
{
c = s[i] - 'a';
k = ch[u][c];
while (k > 1) // 跳到 0 结点自动退出循环
{
ans += bo[k]; // 单词末尾-1 非单词末尾-0
bo[k] = 0; // 防止重复计算
k = nxt[k]; // 通过 nxt 往回跳
}
u = ch[u][c];
}
return;
}
int main()
{
int t, n;
char s[1000010];
scanf("%d", &t);
while (t--)
{
ans = 0;
cnt = 1;
memset(bo, 0, sizeof(bo));
for (int i = 0; i < 26; ++i)
ch[0][i] = 1, ch[1][i] = 0;
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
{
scanf("%s", s);
make(s);
}
bfs();
scanf("%s", s);
find(s);
printf("%d\n", ans);
}
return 0;
}AC 自动机的关键点与 KMP 一样，需要构建出失配指针 fail[] 数组（也就是 KMP 的 next[] ）。
fail[] 构建的核心代码（即下面程序中的 nxt[] ）
void bfs()
{
for (int i = 0; i <= 25; ++i)
ch[0][i] = 1; // 0 结点的每一个字符都指向 root 结点（初始化）
que[1] = 1;
nxt[1] = 0; // 构建 nxt 数组，root 默认指向 0 结点
for (int q1 = 1, q2 = 1; q1 <= q2; ++q1) // BFS
{
int u = que[q1];
for (int i = 0; i <= 25; ++i)
{
if (!ch[u][i]) // 如果到叶子结点的话则通过 nxt 往回跳
ch[u][i] = ch[nxt[u]][i];
else
{
que[++q2] = ch[u][i];
int v = nxt[u];
// 符合条件的 v ：查找父亲的前缀指针(nxt)指向的节点，通过 nxt 一直跳，
// 直到找到该结点的有通过 i 连接的儿子
while (v > 0 && !ch[v][i]) // 通过 nxt 一直跳直到找到符合的
v = nxt[v];
nxt[ch[u][i]] = ch[v][i]; // nxt 的跳转
}
}
}
}注：部分资料来源于百度百科