救救我QAQ

回复帖子

@東方零闇 2019-06-25 19:54 回复

不知道为什么,第二点WA了,但是数据很大又下不了QAQ

#include<bits/stdc++.h>
#define scf scanf
#define ptf printf
#define ll long long
#define Rint register int 
#define forup(i,a,b) for(Rint i=a;i<=b;i++)
using namespace std;
const int N=1e7+101;
const int Z=30;
int num[N],ch[N][Z],nex[N],p[N];
int answer=0,cnt;
bool vis[N];
char s[N<<1];
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-')
            f=-1;
        ch=getchar();   
    }
    while(isdigit(ch)){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
inline void build(char *s){
    int u=0,len=strlen(s);  
    for(int i=0;i<len;i++){
        int c=s[i]-'a';
        if(!ch[u][c]){
            ch[u][c]+=(++cnt);
            memset(ch[cnt],0,sizeof ch[cnt]);
        }
        u=ch[u][c];
    }
    num[u]++;
    vis[u]=true;
    return ;
}
inline void bfs(){
    for(int i=0;i<=25;++i)
        ch[0][i]=1;
    p[1]=1,nex[1]=0;
    for(int i=1,j=1;i<=j;i++){
        int u=p[i];
        forup(i,0,25){
            if(!ch[u][i])
                ch[u][i]=ch[nex[u]][i];
            else{
                p[++j]=ch[u][i];
                nex[ch[u][i]]=ch[nex[u]][i];
            }
        }
    }   
    return ;
}
inline void find(char *s){
    int u=0,len=strlen(s);
    for(int i=0;i<len;i++){
        int c=s[i]-'a',j=ch[u][c];
        while(j>0){
            if(num[j]==-1)
                break;
            answer+=num[j];
            num[j]=-1;
            j=nex[j];
        }
        u=ch[u][c];
    }
    return ;
}
int main(){
        answer=0,cnt=1;
        memset(num,0,sizeof num);
        memset(vis,false,sizeof vis);
        forup(i,0,25)   
            ch[0][i]=1,ch[1][i]=0;
        int n=read();
        forup(i,1,n){
            scf("%s",s);
            build(s);           
        }
        bfs();
        scf("%s",s);
        find(s);
        ptf("%d\n",answer);
        return 0;
}
反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



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