BZOJ 3473 字符串

思路

广义SAM的题目，先全部插入，然后每个字符串在SAM上匹配，如果发现当前sz小于k（就是前缀不满足条件），就跳fail（找前缀的后缀，就是找子串）到满足条件为止，然后一个满足条件的节点，它的所有parent Tree上的祖先也必定满足条件，所以一个满足条件的节点的贡献就是它的maxlen

ps:貌似求sz除了我这种，还可以set启发式合并

代码

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <string>

#include <iostream>

#include <queue>

using namespace std;

int maxlen[201000],minlen[201000],trans[201000][26],suflink[201000],ans[201000],sz[201000],last[201000],endpos[201000],Nodecnt,n;

string s[101000];

int New_state(int _maxlen,int _minlen,int *_trans,int _sz,int _last,int _suflink){

    ++Nodecnt;

    maxlen[Nodecnt]=_maxlen;

    minlen[Nodecnt]=_minlen;

    if(_trans)

        for(int i=0;i<26;i++)

            trans[Nodecnt][i]=_trans[i];

    sz[Nodecnt]=_sz;

    last[Nodecnt]=_last;

    suflink[Nodecnt]=_suflink;

    return Nodecnt;

}

void update(int u,int x){

    while(u&&last[u]!=x){

        last[u]=x;

        sz[u]++;

        u=suflink[u];

    }

}

int add_len(int u,int c,int inq){

    if(trans[u][c]){

        int v=trans[u][c];

        if(maxlen[v]==maxlen[u]+1){

            update(v,inq);

            endpos[v]++;

            return v;

        }

        int y=New_state(maxlen[u]+1,0,trans[v],sz[v],last[v],suflink[v]);

        suflink[v]=y;

        minlen[v]=maxlen[y]+1;

        while(u&&trans[u][c]==v){

            trans[u][c]=y;

            u=suflink[u];

        }

        minlen[y]=maxlen[suflink[y]]+1;

        update(y,inq);

        return y;

    }

    else{

        int z=New_state(maxlen[u]+1,0,NULL,0,0,0);

        endpos[z]=1;

        while(u&&trans[u][c]==0){

            trans[u][c]=z;

            u=suflink[u];

        }

        if(!u){

            suflink[z]=1;

            minlen[z]=1;

            update(z,inq);

            return z;

        }

        int v=trans[u][c];

        if(maxlen[v]==maxlen[u]+1){

            suflink[z]=v;

            minlen[z]=maxlen[v]+1;

            update(z,inq);

            return z;

        }

        int y=New_state(maxlen[u]+1,0,trans[v],sz[v],last[v],suflink[v]);

        suflink[v]=suflink[z]=y;

        minlen[v]=minlen[z]=maxlen[y]+1;

        while(u&&(trans[u][c]==v)){

            trans[u][c]=y;

            u=suflink[u];

        }

        minlen[y]=maxlen[suflink[y]]+1;

        update(z,inq);

        return z;

    }

}

int k,in[200100];

queue<int> q;

int main(){

    freopen("test.in","r",stdin);

    freopen("test.out","w",stdout);

    Nodecnt=1;

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

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

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

        cin>>s[i];

        int last=1,len=s[i].length();

        // cout<<len<<endl;

        for(int j=0;j<len;j++)

            last=add_len(last,s[i][j]-'a',i);

    }

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

        int lent=s[i].length(),p=1;

        // cout<<"!"<<lent<<endl;

        int ans=0;

        for(int j=0;j<lent;j++){

            p=trans[p][s[i][j]-'a'];

            while(sz[p]<k)

                p=suflink[p];

            if(p==0){

                p=1;

                continue;

            }

            ans+=(maxlen[p]);

        }

        printf("%d ",ans);

    }

    return 0;

}

巴特西

BZOJ 3473 字符串

思路

代码

最新文章

热门文章