- #include<bits/stdc++.h>
- using namespace std;
- const int N=1e6+10;
- char s[N];
- int n,tot,tr[N][30],fail[N],end[N];
- void insert(){
- int len=strlen(s+1),now=0;
- for(int i=1;i<=len;++i){
- if(!tr[now][s[i]-'a']) tr[now][s[i]-'a']=++tot;
- now=tr[now][s[i]-'a'];
- }end[now]+=1;
- }
- void build(){
- queue<int>q;
- for(int i=0;i<26;++i)
- if(tr[0][i]){
- fail[tr[0][i]]=0;
- q.push(tr[0][i]);
- }
- while(q.size()){
- int x=q.front();q.pop();
- for(int i=0;i<26;++i){
- if(tr[x][i]){
- int v=tr[x][i];
- fail[v]=tr[fail[x]][i];
- q.push(v);
- }else tr[x][i]=tr[fail[x]][i];
- }
- }
- }
- int query(){
- int res=0,len=strlen(s+1),now=0;
- for(int i=1;i<=len;++i){
- int ch=s[i]-'a';
- now=tr[now][ch];
- for(int t=now;t&&end[t]!=-1;t=fail[t])
- res+=end[t],end[t]=-1;
- }
- return res;
- }
- int main(){
- scanf("%d",&n);
- for(int i=1;i<=n;++i) scanf("%s",s+1),insert();
- build();
- scanf("%s",s+1);
- printf("%d\n",query());
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2915707.html