10195: 「一本通 2.4 例 1」Keywords Search
内存限制：512 MB
时间限制：1.000 S
提交：2
解决：0
评测方式：文本比较
命题人：
题目描述
输入
第一行一个整数 $T$，表示数据组数；
对于每组数据，第一行一个整数 $n$，接下去 $n$ 行表示 $n$ 个单词，最后一行输入一个字符串，表示文章。
输出
对于每组数据，输出一个数，表示文中出现了多少个待查询的单词。
样例输入 复制
1
5
she
he
say
shr
her
yasherhs样例输出 复制
3提示
数据范围：对于全部数据，$1\le n\le 10^4,1\le m\le 10^6$。
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;//ed[i]:这个节点是多少单词的结尾
int tr[N][26],idx=1,ed[N],fk[N];
void insert(string t){
int zz=0;
for(int i=0;i<t.size();i++){
int j=t[i]-'a';//字母映射下标
if(tr[zz][j]==0){
tr[zz][j]=idx++;
}
zz=tr[zz][j];
}//单词结尾
ed[zz]++;
}
void build(){
queue<int> q;//为了层序遍历
for(int i=0;i<26;i++){
if(tr[0][i]) q.push(tr[0][i]);
}
while(q.size()){
int f=q.front(); q.pop();
for(int i=0;i<26;i++){
int c=tr[f][i];//c child 子节点
if(c){//回 fk[]
fk[c]=tr[fk[f]][i];
q.push(c);
}else{//转移 tr[] 虚拟节点
tr[f][i]=tr[ fk[f] ][i];
}
}
}
}
int main(){
int n;
cin>>n;
while(n--){
string t;
cin>>t;
insert(t);
}
build();
string s; int ans=0;
cin>>s;
int zz=0;
for(int i=0;i<s.size();i++){
zz=tr[zz][s[i]-'a'];
for(int j=zz;j&&ed[j]!=-1;j=fk[j]){
ans+=ed[j];
ed[j]=-1;
}
}
cout<<ans;
return 0;
}