Hdu 2222
AC自动机模板题，注意重复关键字的处理
2017.11.18 重写
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
int n, sz = 500000, ch[500000 + 5][30], val[500000 + 5], tms[500000 + 5], lst[500000 + 5], f[500000 + 5], used[10000 + 5];
//n，节点时间戳，字典树数组，是否是单词, 单词出现个数，上一个单词位置(后缀链接)，失配函数，该单词是否记录过
char s[1000000 + 5];
int ans;//答案
void g(int u) {//统计
if (!used[val[u]] && u) ans += tms[u], used[val[u]] = true, g(lst[u]);
//如果没有记录过并且有单词(u!=0), 则加上数量继续向下递归处理
}
void insert(char *s, int u, int ith, int a, int len) {//插入一个单词(递归更新，不建议)
int c = s[a] - 'a';
if (ch[u][c] == 0) ch[u][c] = ++sz;//新建节点
if (a == len - 1) val[ch[u][c]] = ith, tms[ch[u][c]]++; else insert(s, ch[u][c], ith, a + 1, len);
//如果是最后一个要加是单词的标记，并且注意重复的单词
}
void insert(char *s, int ith) {//插入一个单词(迭代更新，建议)
int now = 0, len = strlen(s);
for (int i = 0; i < len; i++) {
int c = s[i] - 'a';
if (!ch[now][c]) ch[now][c] = ++sz;//新建节点
now = ch[now][c];
if (i == len - 1) val[now] = ith, tms[now]++;
//如果是最后一个要加是单词的标记，并且注意重复的单词
}
}
void find(char *T) {//用字符串T当做文本串找模式串
int len = strlen(T), j = 0;//从0开始
for (int i = 0; i < len; i++) {
int c = T[i] - 'a';
j = ch[j][c];
if (val[j]) g(j); else if (lst[j]) g(lst[j]);//如果当前位置有单词或者有上一个单词(不会多余, 例子1看代码末行)则处理
}
}
void getFail() {//得到失配函数
queue<int> q;
f[0] = 0;//初始化开始点的失配函数为0
for (int c = 0; c < 26; c++) {//初始化所以与0相连的点
int v = ch[0][c];
if (v) q.push(v), f[v] = 0, lst[v] = 0;
}
while (!q.empty()) {//bfs更新
int u = q.front(); q.pop();
for (int c = 0; c < 26; c++) {
int v = ch[u][c];
if (!v) {ch[u][c] = ch[f[u]][c]; continue;} //Trie上没有这条边
q.push(v);
int j = f[u]; while (j && !ch[j][c]) j = f[j];//沿着失配边走
f[v] = ch[j][c], lst[v] = (val[f[v]]) ? (f[v]) : (lst[f[v]]);
//得到失配函数值，求出lst值
}
}
}
void clean() {//清除
for (int i = 0; i <= sz; i++) {
for (int j = 0; j < 26; j++) ch[i][j] = 0;
f[i] = lst[i] = val[i] = tms[i] = 0;
}
for (int i = 0; i <= n; i++) used[i] = false;
sz = 0;
}
void solve() {
scanf("%d", &n);
clean();
for (int i = 1; i <= n; i++) {
scanf("%s", s);
//insert(s, 0, i, 0, strlen(s));//递归
insert(s, i);//迭代
}
scanf("%s", s);
getFail(), ans = 0, find(s);
printf("%d\n", ans);
}
int main() {
int T; scanf("%d", &T);
while (T--) solve();
return 0;
}
/*
例子1：
1
2
errd
rr
errd
如果不执行该语句，rr则不能被算入
*/
旧：
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#define ms(i,j) memset(i,j, sizeof i);
using namespace std;
const int MAXN = 10000 + 5, _SIZE = 26;
int n;
struct acam
{
int sz;//结点编号
int res;
int ch[MAXN*51][_SIZE];//Tire
int last[MAXN*51];//后缀链接
int f[MAXN*51];//失配函数
int val[MAXN*51][2];//结点的权值
bool used[MAXN*51];//用过
void init()//初始化
{
ms(val,0);
ms(ch,0);
ms(used,false);
sz = 1;
res = 0;
}
void insert(char *s, int v)//插入一个模板
{
int u = 0;
int len = strlen(s);
for (int i=0;i<len;i++)
{
int c = s[i] - 'a';
if (ch[u][c])
{
u = ch[u][c];
} else
{
ch[u][c] = ++sz;
u = ch[u][c];
}
if (i==len-1)
{
val[u][0] = v;
val[u][1]++;
}
}
}
void g(int j)//递归更新cnt
{
if (j&&!used[val[j][0]])
{
res+=val[j][1];
used[val[j][0]] = true;
g(last[j]);
}
}
void find(char *T)//在T中匹配
{
int len = strlen(T);
int j = 0;
for (int i=0;i<len;i++)
{
int c = T[i] - 'a';
j = ch[j][c];
if (val[j][0]) g(j);
else if (last[j]) g(last[j]);
}
}
void getFail()//获得失配函数
{
queue<int> q;
f[0] = 0;
for (int c=0;c<_SIZE;c++)//初始化进队
{
int u = ch[0][c];
if (u)
{
q.push(u);
f[u] = 0;
last[u] = 0;
}
}
while (!q.empty())
{
int r = q.front(); q.pop();
for (int c=0;c<_SIZE;c++)
{
int u = ch[r][c];
if (!u)
{
ch[r][c] = ch[f[r]][c];
continue;
}
q.push(u);
int j = f[r];
while (j&&!ch[j][c]) j = f[j];
f[u] = ch[j][c];
last[u] = (val[f[u]][0]) ? (f[u]) : (last[f[u]]);
}
}
}
}ac;
char s[1000000 + 5];
int main()
{
int kase;
scanf("%d", &kase);
while (kase--)
{
ac.init();
scanf("%d", &n);
for (int i=1;i<=n;i++)
{
scanf("%s", s);
ac.insert(s,i);
}
scanf("%s", s);
ac.getFail();
ac.find(s);
printf("%d\n", ac.res);
}
return 0;
}
