Description

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

Input

第一行一个n，表示模式串个数；

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

下面一行一个文本串。

Output

一个数表示答案

Sample Input

1
2
3
4
2
a
aa
aa

Sample Output

1
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]$ 继续匹配
{:.info}

Code

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
#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;
}