AC自动机(简单版)

Description

给定n个模式串和1个文本串,求有多少个模式串在文本串里出现过。

Input

第一行一个n,表示模式串个数;

下面n行每行一个模式串;

下面一行一个文本串。

Output

一个数表示答案

Sample Input

2
a
aa
aa

Sample Output

2

Hint

# Data Range
SubTask1(50) $\sum len(模式串,文本串)\leq10^6\;n=1$
SubTask2(50) $\sum len(模式串,文本串)\leq10^6$

分析

看题目名字就知道这是一道AC自动机裸题

回顾一下AC自动机的算法流程:

  1. 所有模式串建立Trie树:$Tinsert$
  2. 建立 lose 数组(fail指针):$Tinit$
  3. 匹配:$Tmatch$

在匹配过程中,由于要防止后缀重复出现的问题,每走过一个节点,将他的 $isend$ 值设置为 $false$ ,为了防止前缀相同而漏掉,需要每次 $k=lose[k]$ 继续匹配

Code

#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
#define maxc 26
#define maxn 1000001
using namespace std;
struct node{
	int to[maxc];
	int isend;
}g[maxn];
int lose[maxn]; int tot=1;
inline void Tinsert(char *t){
	int lent=strlen(t); char c;
	int u=1;
	for(int i=0;i<lent;i++){
		c=t[i]-'a';
		if(!g[u].to[c])
			g[u].to[c]=++tot;
		u=g[u].to[c];
	}
	g[u].isend++;
}
inline void Tinit(){
	queue<int> q;
	for(int i=0;i<26;i++) g[0].to[i]=1;
	q.push(1); lose[1]=0; int head;
	#define head2 lose[head]
	while(!q.empty()){
		head=q.front(); q.pop();
		for(int i=0;i<26;i++){
			if(!g[head].to[i])
				g[head].to[i]=g[lose[head]].to[i];
			else{
				q.push(g[head].to[i]);
				lose[g[head].to[i]]=g[head2].to[i];
			}
		}
	}
	#undef head2
}
inline int Tmatch(char *s){
	int lens=strlen(s);
	int u=1; int c,k; int ans=0;
	for(int i=0;i<lens;i++){
		c=s[i]-'a';
		u=g[u].to[c];
		for(k=u;k!=0 && g[k].isend!=-1;k=lose[k]){
			ans+=g[k].isend;
			g[k].isend=-1;
		}
	}
	return ans;
}
char A[maxn],R[maxn];
int n;
int main(){
	#ifndef ONLINE_JUDGE
	freopen("testin.txt","r",stdin);
	freopen("testout.txt","w",stdout);
	#endif
	cin>>n;
	for(int i=1;i<=n;i++)
		scanf("%s",A),Tinsert(A);
	scanf("%s",R);
	Tinit();
	cout<<Tmatch(R);
	return 0;
}