BZOJ 3277 串 & BZOJ 3473 字符串 (广义后缀自动机、时间复杂度分析、启发式合并、线段树合并、主席树)

标签那么长是因为做法太多了。。。

题目链接: (bzoj 3277) https://www.lydsy.com/JudgeOnline/problem.php?id=3277

(bzoj 3473) https://www.lydsy.com/JudgeOnline/problem.php?id=3473

题解:

先讲三个做法公共部分: 建出广义SAM，然后对于每个点求出它在多少字符串中出现过。

做法一

把每个字符串在广义SAM上暴力跑。每跑到一个点就暴力沿着fail树往上跳，标记跳过的点，直到跳到已标记的点为止(每个串要换用不同的标记)。

时间复杂度\(O(L\sqrt L)\) (\(n\)为串的个数，\(L\)为总长度)

写一下时间复杂度分析: (我自己想的，很有可能是错的，有错恳请大佬指出！！感谢)

假设某个字符串长度为\(x\), 则最坏情况下它一直在往深处走，并且每一步都没有碰到已经跳过的点，这种情况下其走的步数是\(\sum^{x}_{i=1}i=O(x^2)\).

但是它还要受到另一个限制，就是走的步数不超过SAM总大小\(O(L)\). 因此其对时间复杂度贡献为\(O(\min(x^2),L)\).

计算最坏情况下的时间复杂度，也就是已知\(\sum^{m}_{i=1} x_i=L\), 求\(\sum^{m}_{i=1} \min(x_i^2,L)\)的最大值。显然当\(x_i>\sqrt L\)时是没有任何意义的(白白浪费代价，价值不增加)，所以就是已知\(\sum^{m}_{i=1} x_i=L\)且对于任意\(i\)有\(i\le \sqrt L\), 求\(\sum^{m}_{i=1} x_i^2\)的最大值。由函数的凹凸性知显然(或者也可以用偏导数解释，如果你愿意的话。。。)所有串长均为\(\sqrt L\)时目标函数最大，为\(O(L\sqrt L)\).

做法二

类似于BZOJ2754/BZOJ2780, 就是个数颜色问题，每个点开个set记录经过这个点的所有串，然后沿着Parent树自下而上启发式合并。时间复杂度\(O(n\log^2n)\).

线段树合并貌似可以做到\(O(n\log n)\)?

做法三

依然是数颜色，可以使用DFS序+主席树等各种神奇做法解决。时间复杂度\(O(n\log^2n)\) (?)

代码

做法一

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<string>

#include<vector>

#define llong long long

using namespace std;

const int N = 4e5;

const int S = 26;

struct SAM

{

    int id[N+3];

    int fa[N+3];

    int son[N+3][S+3];

    int len[N+3];

    int sz[N+3];

    int buc[N+3];

    int oid[N+3];

    int cnt[N+3];

    int cid[N+3];

    int mx[N+3];

    int siz,rtn,lstpos;

    void init() {id[0] = siz = rtn = lstpos = 1;}

    int insertstr(char ch)

    {

        int p = lstpos,np; siz++; np = lstpos = siz; len[np] = len[p]+1; sz[np] = 1;

        for(; p && son[p][ch]==0; p=fa[p]) {son[p][ch] = np;}

        if(p==0) fa[np] = rtn;

        else

        {

            int q = son[p][ch];

            if(len[q]==len[p]+1) {fa[np] = q;}

            else

            {

                siz++; int nq = siz; len[nq] = len[p]+1;

                memcpy(son[nq],son[q],sizeof(son[q]));

                fa[nq] = fa[q]; fa[np] = fa[q] = nq;

                for(; p && son[p][ch]==q; p=fa[p]) {son[p][ch] = nq;}

            }

        }

        return np;

    }

    void getsort()

    {

        for(int i=1; i<=siz; i++) buc[len[i]]++;

        for(int i=1; i<=siz; i++) buc[i] += buc[i-1];

        for(int i=siz; i>=1; i--) oid[buc[len[i]]--] = i;

    }

} sam;

vector<char> str[N+3];

char a[N+3];

int n,m;

int main()

{

    scanf("%d%d",&n,&m);

    sam.init();

    for(int i=1; i<=n; i++)

    {

        scanf("%s",a+1);

        sam.lstpos = 1;

        int lena = strlen(a+1);

        for(int j=1; j<=lena; j++) {sam.insertstr(a[j]-96); str[i].push_back(a[j]);}

    }

//  for(int i=1; i<=sam.siz; i++) for(int j=1; j<=S; j++) if(sam.son[i][j]) printf("trans%d %d %d\n",i,j,sam.son[i][j]);

//  for(int i=1; i<=sam.siz; i++) printf("i%d len%d fa%d\n",i,sam.len[i],sam.fa[i]);

    sam.getsort();

    for(int i=1; i<=n; i++)

    {

        int pos = sam.rtn;

        for(int j=0; j<str[i].size(); j++)

        {

            pos = sam.son[pos][str[i][j]-96];

            int tmp = pos;

            for(; tmp && sam.cid[tmp]!=i; tmp=sam.fa[tmp]) {sam.cnt[tmp]++; sam.cid[tmp] = i;}

        }

    }

    sam.cnt[1] = 0;

    for(int i=1; i<=sam.siz; i++)

    {

        int u = sam.oid[i];

        sam.mx[u] = sam.mx[sam.fa[u]]+(sam.cnt[u]>=m ? sam.len[u]-sam.len[sam.fa[u]] : 0);

//      printf("%d mx%d\n",u,sam.mx[u]);

    }

    for(int i=1; i<=n; i++)

    {

        int pos = sam.rtn; llong ans = 0ll;

        for(int j=0; j<str[i].size(); j++)

        {

            pos = sam.son[pos][str[i][j]-96];

            ans += (llong)sam.mx[pos];

//          putchar(str[i][j]); printf("pos%d\n",pos); puts("");

        }

        printf("%lld ",ans);

    }

    return 0;

}