#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define lf long double
#define INF 0x7fffffff
#define debug(alpha) cout<<alpha<<endl
#define min(a,b) (a>b?b:a)
#define max(a,b) (a>b?a:b)
#define Max3(a,b,c) (max(max((a),(b)),(c)))
#define Min3(a,b,c) (min(min((a),(b)),(c)))
using namespace std;
namespace io
{
template<typename T> inline void iread(T &x114){
char c=' ';int wx114=1;x114=0;
while(!isdigit(c)){c=getchar();if(c=='-')wx114=-1;}
while(isdigit(c)){x114=x114*10+c-'0';c=getchar();}
x114*=wx114;
}
template<typename T> inline void write(T x114){
if(x114==0){putchar('0');return;}
if(x114<0){putchar('-');x114=-x114;}
int stk[50],top=0;
while(x114){stk[++top]=x114%10;x114/=10;}
while(top) putchar(stk[top--]+'0');
}
}
/**
* AC自动机是一个很好用的东西
* 完美融合了KMP和Trie
* 多模式串匹配非常有效率
* 大体思路就是把模式串建成一棵Trie
* 然后拉出各种失配指针,失配就去到另一个节点
* 最后统计出来结果
* 总之对初学者来讲,难度较高
*/
const int N=1e6+100;
int n;// 模式串个数
struct node
{
int son[26];// 每个Trie节点都有a~z儿子(有些为空)
// 以及转移边
/*
转移边就是在我失配的情况下,我转移到另一个模式串去
一个节点可以有多条转移边,但只有一条回跳边
*/
}trie[N];
int idx;// 最新节点编号
// 根节点是0
int cnt[N];// 以该节点为结尾的单词数
void insert(string s)// 插入一个模式串,不会复习Trie
{
int l=s.length(),p=0;
for(int i=0;i<l;++i)
{
char c=s[i];
if(!trie[p].son[c-'a'])
trie[p].son[c-'a']=++idx;
p=trie[p].son[c-'a'];
}
++cnt[p];
}
int fail[N];// 回跳边存储,指向回跳的位置
void build()// 建立转移边和回跳边
{
queue<int> q;
for(int i=0;i<26;++i)
if(trie[0].son[i])// 只要我这个位置有数据
q.push(trie[0].son[i]);// 作为起点
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=0;i<26;++i)
{
if(trie[u].son[i])// 我有对应的儿子,建立回跳边
{
fail[trie[u].son[i]]=trie[fail[u]].son[i];
// 我儿子的回跳边是 我回跳边所指的节点的 对应的儿子
q.push(trie[u].son[i]);
}
else// 我没有对应的儿子,建立转移边
trie[u].son[i]=trie[fail[u]].son[i];
// 直接指向我回跳边所指节点的 对应的儿子
// 总之我有儿子就让儿子指,没儿子我自己指
}
}
}
int query(string s)// 查找模式串
{
int l=s.length();
int ans=0;// 记录答案数
for(int k=0,i=0;k<l;++k)
{
// 这里i是一个指针,指向现在所遍历的位置
i=trie[i].son[s[k]-'a'];
for(int j=i;j&&(~cnt[j]);j=fail[j])
{
// 如果~cnt[i]==false,说明之前走过了,撤退
// 不然还可以接着回跳边跳
ans+=cnt[j];
cnt[j]=-1;
}
}
return ans;
}
string sss;
signed main()
{
cin>>n;
for(int i=1;i<=n;++i)
{
cin>>sss;
insert(sss);
}
cin>>sss;
cout<<query(sss);
return 0;
}
多行注释之前的不用管,下面的代码第二个点WA了