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