第二个点咋调都是WA;心态大蹦 有大佬帮忙看看吗
查看原帖
第二个点咋调都是WA;心态大蹦 有大佬帮忙看看吗
356606
PJSSABER楼主2021/1/12 18:04

第一个点能过

#include <bits/stdc++.h>

#define ll long long
#define forplus(i,j,n) for(int i=j;i<=n;i++)
#define forminus(i,j,n) for(int i=n;i>=j;i--)
#define pii pair<int,int>
#define clr(x) memset(x,0,sizeof x)
#define clrmax(x) memset(x,0x3f,sizeof x)
#define clrmin(x) memset(x,INT_MIN,sizeof x)

using namespace std;

int n;
const int maxnode=1e6+5;

struct Trie{
    int ch[maxnode][26];
    int val[maxnode];
    int last[maxnode]; //后缀链接
    int sz=1,ans=0;

    inline int idx(char c)
    {
        return c-'a';
    }

    void push(string ca)
    {
        int root=0; 
        int len=ca.size();
        for(int i=0;i<len;i++)
        {
            int cur=idx(ca[i]);
            if(!ch[root][cur])
            {
                clr(ch[sz]);
                val[sz]=0;
                ch[root][cur]=sz++;
            }
            root=ch[root][cur];
       
        } 
        val[root]++;
    }

    int f[maxnode];

    void getf()
    {
        clr(f);
        clr(last);

        queue<int> q;
        f[0]=0;

        forplus(i,0,25)
        {
            if(ch[0][i])
            {
                int j=ch[0][i];
                f[j]=0;
                q.push(j);
            }
        }

        while(!q.empty())
        {
            int x=q.front();q.pop();
            int j=f[x];

            for(int i=0;i<26;i++)
            {
                int u=ch[x][i];
                if(u)
                {
                    q.push(u);
                    while(j && !ch[j][i]) j=f[j];
                    f[u]=ch[j][i];
                    
                    if(val[f[u]])
                        last[u]=f[u];
                    else
                        last[u]=last[f[u]];
                }
                else
                    f[ch[x][i]]=ch[j][i];
            }
        }

    }

    void find(string text)
    {
        ans=0;
        int root=0,id;
        int len=text.size();
        for(int i=0;i<len;i++)
        {
            id=idx(text[i]);

            while(root && !ch[root][id]) 
                root=f[root];

            root=ch[root][id];

            if(val[root])
            {
                ans+=val[root];
                val[root]=0;
            }

            int tp=root;
            while(last[tp])
            {
                tp=last[tp];
                ans+=val[tp];
                val[tp]=0;
            }
        }
    }
};

Trie tries;

string tmp,text;


int main()
{
    ios::sync_with_stdio(false);
    
    cin>>n;

    forplus(i,1,n)
    {
        cin>>tmp;
        tries.push(tmp);
    }
    tries.getf();
    cin>>text;
    tries.find(text);
    cout<<tries.ans<<endl;

    return 0;
}
2021/1/12 18:04
加载中...