BZOJ 3277/3473 广义后缀自动机

说实话没啥难的.

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

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

要注意每个串中相同的子串的贡献是都要加进去的，开始因为这个被坑了好久 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;

}