求大佬查错
查看原帖
求大佬查错
181715
gjh303987897楼主2022/1/20 15:47
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int n,num;
struct data{
    int son[26];
    int flag;
    int fail;
}t[1000001];
void build(char *s){
    int len=strlen(s);
    int begin=0;
    for(int i=0;i<len;i++){
        int x=s[i]-'a';
        if(!t[begin].son[x]) t[begin].son[x]=++num;
        begin=t[begin].son[x];
    }
    t[begin].flag++;
}
int point,que[1000001];
int head=1;
void ACauto_build_next(){
    for(int i=0;i<=25;i++){
        if(!t[0].son[i]){
            t[t[0].son[i]].fail=0;
            que[++point]=t[0].son[i];
        }
    }
    for(int i=head;i<=point;i++){
        int now=que[head]; head++;
        for(int j=0;j<26;j++){
            if(t[now].son[j]){
                t[t[now].son[j]].fail=t[t[now].fail].son[j];
                que[++point]=t[now].son[j];
            }
            else{
                t[now].son[j]=t[t[now].fail].son[j];
            }
        }
    }
}
int ACauto_find(char *s){
    int len=strlen(s);
    int now=0,ans=0;
    for(int i=0;i<len;i++){
        int x=s[i]-'a';
        now=t[now].son[x];
        for(int j=now;j && t[j].flag;j=t[j].fail){
            ans+=t[j].fail; t[j].fail=0;
        }
    }
    return ans;
}
int main()
{
    scanf("%d",&n);char s1[1010101];
    for(int i=1;i<=n;i++){
        cin>>s1; build(s1);
    }
    ACauto_build_next(); cin>>s1;
    int ans=ACauto_find(s1);
    printf("%d",ans);
    return 0;
}
2022/1/20 15:47
加载中...