BZOJ 3277/3473 广义后缀自动机

我会带着你远行 2021-09-30 10:26 273阅读 0赞

说实话没啥难的.

建一棵广义后缀自动机，暴力自底向上更新即可.

时间复杂度非常玄学，但据说是可以过的.

要注意每个串中相同的子串的贡献是都要加进去的，开始因为这个被坑了好久 QAQ

Code:

#include <cstdio>
    #include <algorithm>
    #include <vector> 
    #include <cstring>
    #include <string>
    #define setIO(s) freopen(s".in","r",stdin) 
    #define maxn 300000
    #define N 30 
    using namespace std;
    int m,k,n,length[maxn]; 
    char str[maxn];
    string s[maxn];
    struct SAM{
        int last,tot;
        int ch[maxn][N], f[maxn],cnt[maxn],len[maxn],C[maxn],rk[maxn],mk[maxn];
        long long sumv[maxn]; 
        void init() { last = tot = 1; }
        void ins(int c){
            int p=last,np,nq;
            if(ch[p][c]){          
                int q=ch[p][c];                
                if(len[q]==len[p]+1) last=q; 
                else 
                {        
                    nq=++tot,last=nq; 
                    f[nq]=f[q],f[q]=nq,len[nq]=len[p]+1; 
                    memcpy(ch[nq],ch[q],sizeof(ch[q]));
                    while(p&&ch[p][c]==q)ch[p][c]=nq,p=f[p];            
                }
            }      
            else {
                np=++tot,last=np,len[np]=len[p]+1; 
                while(p&&!ch[p][c]) ch[p][c]=np,p=f[p];
                if(!p) f[np]=1;
                else {    
                    int q=ch[p][c];
                    if(len[q]==len[p]+1) f[np]=q; 
                    else 
                    {
                        nq=++tot;
                        f[nq]=f[q],f[q]=f[np]=nq,len[nq]=len[p]+1;
                        memcpy(ch[nq],ch[q],sizeof(ch[q]));
                        while(p&&ch[p][c]==q) ch[p][c]=nq,p=f[p];
                    }
                }    
    
            }
        }
        void Solve(){
            for(int i = 1;i <= m; ++i) {
                int p = 1,c,u;
                for(int j = 0;j < length[i]; ++j) {
                    c = s[i][j] - 'a'; p = ch[p][c]; u = p;
                    while(u && mk[u] != i) ++cnt[u],mk[u] = i,u = f[u];
                }
            }
            for(int i = 1;i <= tot; ++i) C[len[i]]++;
            for(int i = 1;i <= tot; ++i) C[i] += C[i - 1];
            for(int i = 1;i <= tot; ++i) rk[C[len[i]]--] = i;
            for(int i = 1;i <= tot; ++i) 
            {
                int t = rk[i];
                sumv[t] = cnt[t] >= k ? sumv[f[t]] + (len[t] - len[f[t]]) : sumv[f[t]]; 
            }
            for(int i = 1;i <= m; ++i) 
            {
                int p = 1;
                long long ans = 0; 
                for(int j = 0;j < length[i]; ++j) {
                    p = ch[p][s[i][j]-'a'];
                    ans += sumv[p];
                }
                printf("%lld ",ans); 
            }
        }
    }T;
    int main() {
        //setIO("input");
        scanf("%d%d",&m,&k),T.init(); 
        for(int i = 1;i <= m; ++i) {
            T.last = 1;
            scanf("%s",str),s[i] = string(str),length[i] = strlen(str);
            for(int j = 0;j < length[i]; ++j) T.ins(s[i][j] - 'a');
        }
        T.Solve(); 
        return 0;
    }

转载于:https://www.cnblogs.com/guangheli/p/10324839.html