1 条题解
-
0wangmaohua20090908 LV 4 @ 2019-08-08 09:24:06
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
struct acauto
{
int fail,num;
int s[30];
}q[1000005];
int cnt;
int zx[1000005];
int er;
int n;
int tonumber(char c)
{
return c-'a'+1;
}
void fuchu(char ss[])
{
int kai=0;
int len=strlen(ss);
bool flag=false;
for(int i=0;i<len;i++)
{
int pp=tonumber(ss[i]);
if(!q[kai].s[pp])q[kai].s[pp]=++cnt;
else if(i==len-1)
{
flag=true;
zx[++er]=q[kai].s[pp];
break;
}
kai=q[kai].s[pp];
}
if(flag)return;
q[kai].num=++er;
}
int que[1000005];
void getfail()
{
q[0].fail=-1;
int h=0,t=0;
while(h<=t)
{
int p=que[h++];
for(int i=1;i<=26;i++)if(q[p].s[i])
{
int fai=q[p].fail;
while(fai!=-1)
{
bool flag=false;
for(int j=1;j<=26;j++)
if(q[fai].s[j])
{
if(i==j)
{
q[q[p].s[i]].fail=q[fai].s[j];
flag=true;
break;
}
}
if(flag)break;
fai=q[fai].fail;
}
que[++t]=q[p].s[i];
}
}
}
char t[1000005];
int cishu[1000005];
int ccc[1000005];
void dfs(int ro)
{
for(int i=1;i<=26;i++)
if(q[ro].s[i])dfs(q[ro].s[i]);
if(ro)ccc[q[ro].fail]+=ccc[ro];
}
void dfs2(int ro)
{
if(q[ro].num)cishu[q[ro].num]=ccc[ro];
for(int i=1;i<=26;i++)if(q[ro].s[i])
{
dfs2(q[ro].s[i]);
}
}
void query()
{
int len=strlen(t);
int rr=0;
for(int i=0;i<len;i++)
{
int ppp=tonumber(t[i]);
if(!q[rr].s[ppp])break;
ccc[q[rr].s[ppp]]=1;
rr=q[rr].s[ppp];
}
rr=0;
for(int i=len-1;i>=0;i--)
{
int ppp=tonumber(t[i]);
if(!q[rr].s[ppp])break;
ccc[q[rr].s[ppp]]=1;
rr=q[rr].s[ppp];
}
dfs(0);
dfs2(0);
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
char s[1000005]={0};
scanf("%s",s);
fuchu(s);
}
scanf("%s",t);
fuchu(t);
getfail();
query();
int ans=0;
for(int i=1;i<=n;i++)
{
int pp=i;
if(zx[i])pp=zx[i];
ans+=!!cishu[pp];
//printf("%d\n",cishu[pp]);
}
printf("%d\n",ans);
return 0;
}错了
- 1