BZOJ3172: [Tjoi2013]单词【AC自动机】

3172: [Tjoi2013]单词

【题目描述】

传送门

【题解】

我们枚举文本串,然后在AC自动机上走,最笨的想法就是每一个点都往pre上跳,当然不行,其实我们不需要每次都跳,标记这个点经过的次数,用前缀和统计就可以了。

代码如下

#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
const int MAXN=1e6+5;
int n,Ans[MAXN],P[MAXN];char S[MAXN];
struct Acho{
    int hd,tl,cnt,Son[MAXN][26],pre[MAXN],que[MAXN],W[MAXN];
    void Insert(char *s,int t){
        int Now=0;
        for(int i=0,Len=strlen(s);i<Len;i++){
            if(!Son[Now][s[i]-'a']) Son[Now][s[i]-'a']=++cnt;
            Now=Son[Now][s[i]-'a'];
        }
        W[t]=Now;
    }
    void Build(){
        hd=tl=0;
        for(int i=0;i<26;i++) if(Son[0][i]) que[++tl]=Son[0][i];
        while(hd^tl){
            int x=que[++hd];
            for(int i=0;i<26;i++){
                if(Son[x][i]){
                    int f=pre[x];
                    while(f&&!Son[f][i]) f=pre[f];
                    pre[que[++tl]=Son[x][i]]=Son[f][i];
                }else Son[x][i]=Son[pre[x]][i];
            }
        }
    }
    void Fnd(char *s,int Len){
        for(int i=0,Now=0;i<Len;i++){
            while(Now&&!Son[Now][s[i]-'a']) Now=pre[Now];
            if(Son[Now][s[i]-'a']) Ans[Now=Son[Now][s[i]-'a']]++;
        }
    }
    void Work(){for(int i=cnt;i;i--) Ans[pre[que[i]]]+=Ans[que[i]];}
}Tre;
int main(){
    #ifndef ONLINE_JUDGE
    freopen("prob.in","r",stdin);
    freopen("prob.out","w",stdout);
    #endif
    scanf("%d",&n);int Len=0;
    for(int i=1;i<=n;i++) scanf("%s",S+Len),P[i]=Len,Tre.Insert(S+Len,i),Len=strlen(S);P[n+1]=Len;
    Tre.Build();
    for(int i=1;i<=n;i++) Tre.Fnd(S+P[i],P[i+1]-P[i]);
    Tre.Work();
    for(int i=1;i<=n;i++) printf("%d\n",Ans[Tre.W[i]]);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部