#include<iostream> #include<cstdio> #include<queue> #include<stack> #include<cstring> #include <cctype> using namespace std; inline void read(int &x) { x=0;int f=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-') f=-1; c=getchar();} while(c<='9'&&c>='0'){x=(x<<1)+(x<<3)+(c^48);c=getchar();} x*=f; } inline void print(int x) { if(x<0){x=-x;putchar('-');} if(x>9) print(x/10); putchar(x%10+'0'); } int n,sum; char p[1000100]; int trie[500500][26]; int mk[500500];//标记次节点单词个数 int faq[500500]; //失配指针 queue<int>q; int main() { read(n); for(int i=1;i<=n;i++) { scanf("%s",p+1); int len=strlen(p+1),rt=0; for(int j=1;j<=len;j++) { int id=p[j]-'a';p[j]='\0'; if(!trie[rt][id]) trie[rt][id]=++sum; rt=trie[rt][id]; } mk[rt]++; }//建trie树 for(int i=0;i<=25;i++) if(trie[0][i]) faq[trie[0][i]]=0,q.push(trie[0][i]); //与根节点0相连的点的faq全指向0(作为模式串开头字母如果无法匹配只能到根节点上),并把存在的节点进队等待处理 while(!q.empty()) { int u=q.front();q.pop(); for(int i=0;i<=25;i++) { if(trie[u][i]) faq[trie[u][i]]=trie[faq[u]][i],q.push(trie[u][i]); //如果当前位置下有这个字母节点,则其失配指针指向当前位置的失配指针下的该节点; //若当前位置的失配指针下没有当前遍历的该字母节点,任不影响(为0,指向超级节点); else trie[u][i]=trie[faq[u]][i]; //当前位置下没有这个节点;就调到它失配指针所指向的节点下的此个字母节点; //若为0,不影响,指向根节点; } } //造机原理: //若当前节点为A,其父节点为B,B的fail为C,那么C所代表的字符串一定是B的最长的后缀。 //如果C有一个儿子D的字符与A的字符等同,那么显然D所代表的串(C加一个字符)就是A所代表的串(B加一个字符)的最长后缀。 //如果C没有一个儿子,使其字符与A的字符等同呢?很简单,只需要再访问C的fail就行了。 //如此反复,直到A的最长后缀找到,或者A的fail指向根节点为止。 scanf("%s",p+1); int len=strlen(p+1),rt=0,ans=0; for(int i=1;i<=len;i++) { rt=trie[rt][p[i]-'a'];//当前位置的下一个节点位置; for(int j=rt;j&&mk[j];j=faq[j]) ans+=mk[j],mk[j]=0; //当此节点存在同时其单词个数未被统计; //将答案加上所搜索的字符串中所包含的该单词数 ; //标记已经统计 //直接将位置指向其失配指针的位置(节约时间); } printf("%d\n",ans); return 0; }