「bzoj3473 字符串」 - 后缀自动机

电玩女神 2022-01-07 14:43 195阅读 0赞

(好久没有更了,随便放一个)

## 题意 ##

给定 \\(n\\) 个字符串,询问每个字符串有多少子串（不包括空串）是所有 \\(n\\) 个字符串中至少 \\(k\\) 个字符串的子串？

## 题解 ##

建出广义自动机,然后把每个串跑一遍,算下答案就好了  
(后缀自动机写错两个地方调了好久,我真的菜

#include <string>
    #include <cstdio>
    #include <cstring>
    #include <iostream>
    #define rep(i,a,b) for(int i=(a);i<=(b);++i)
    #define N 200005
    typedef long long ll;
    
    int n,k;
    std::string s[N];
    ll ans;
    
    struct SAM{
        int lst,cnt;
        int fa[N],ch[N][26];
        int len[N],tot[N],cur[N];
        int ord[N],bin[N];
        ll f[N];
        SAM(){lst=cnt=1;}
        void extend(int c){
            int p=lst,np=lst=++cnt; len[np]=len[p]+1;
            for (;p&&!ch[p][c];p=fa[p]) ch[p][c]=np;
            if (!p) fa[np]=1;
            else{
                int q=ch[p][c];
                if (len[p]+1==len[q]) fa[np]=q;
                else{
                    int nq=++cnt; len[nq]=len[p]+1;
                    memcpy(ch[nq],ch[q],sizeof(ch[nq])),fa[nq]=fa[q];
                    fa[q]=fa[np]=nq;
                    for (;p&&ch[p][c]==q;p=fa[p]) ch[p][c]=nq;
                }
            }
        }
        void sort(){
            rep (i,1,cnt) ++bin[len[i]];
            rep (i,1,cnt) bin[i]+=bin[i-1];
            rep (i,1,cnt) ord[bin[len[i]]--]=i;
        }
        void solve(){
            rep (i,1,n){
                int u=1;
                rep (j,0,(int)s[i].size()-1){
                    int p=u=ch[u][s[i][j]-'a'];
                    for (;p!=1&&cur[p]!=i;p=fa[p]) ++tot[p],cur[p]=i;
                }
            }
            sort();
            rep (i,1,cnt){
                int p=ord[i];
                f[p]=f[fa[p]]+(tot[p]>=k?len[p]-len[fa[p]]:0);
            }
            rep (i,1,n){
                int p=1; ans=0;
                rep (j,0,(int)s[i].size()-1){
                    p=ch[p][s[i][j]-'a'];
                    ans+=f[p];
                }
                printf("%lld ",ans);
            }
        }
    } sam;
    
    int main(){
        scanf("%d%d",&n,&k);
        rep (i,1,n){
            std::cin>>s[i];
            sam.lst=1;
            rep (j,0,(int)s[i].size()-1) sam.extend(s[i][j]-'a');
        }
        sam.solve();
        return 0;
    }

转载于:https://www.cnblogs.com/xuanyi/p/10638444.html