1 条题解

  • 0
    @ 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

信息

难度
7
分类
字符串 | KMPAC自动机 点击显示
标签
(无)
递交数
37
已通过
8
通过率
22%
上传者