蒟蒻求助,全WA

回复帖子

@2018zys 2019-05-20 19:31 回复
#include<cstdio>
#include<cstring>
#include<queue>
#define N 1000000
using namespace std;
int trie[N+1][31],fail[N+1],cntword[N+1],tot=1;
void insert(char s[])
{
    int len=strlen(s);
    int u=1;
    for(int i=0;i<len;i++)
    {
        int c=s[i]-'a';
        if(trie[u][c]!=0)
            trie[u][c]=++tot;
        u=trie[u][c];
    }
    cntword[u]++;
}
void get_fail()
{
    queue<int> q;
    for(int i=0;i<26;i++)
        if(trie[1][i]!=0)
        {
            fail[trie[1][i]]=1;
            q.push(trie[1][i]);
        }
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=0;i<26;i++)
        {
            if(trie[u][i]!=0)
            {
                fail[trie[u][i]]=trie[fail[u]][i];
                q.push(trie[u][i]);
            }
            else
                trie[u][i]=trie[fail[u]][i];
        }
    }
}
int AC_query(char s[])
{
    int len=strlen(s);
    int u=1,ans=0;
    for(int i=0;i<len;i++)
    {
        u=trie[u][s[i]-'a'];
        for(int j=u;j!=1&&cntword[j]!=-1;j=fail[j])
        {
            ans+=cntword[j];
            cntword[j]=-1;
        }
    }
}
char s[N+1];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%s",s);
        insert(s);
    }
    fail[1]=1;
    get_fail();
    scanf("%s",s);
    printf("%d",AC_query(s));
    return 0;
}
反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。