BZOJ 5261 Rhyme-白红宇

BZOJ 5261 Rhyme

阅读量：6957 次

发布时间：2019-06-27

本文共 3049 字，大约阅读时间需要 10 分钟。

思路

考虑一个匹配的过程，当一个节点x向后拼接一个c的时候，为了满足题目条件的限制，应该向suflink中最深的len[x]+1>=k的节点转移（保证该后缀拼上一个c之后，长度为k的子串依然属于模板串的子串），然后拓扑求最长链即可，出现环就输出INF

代码

#include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;int Nodecnt,trans[250000][26],suflink[250000],maxlen[250000],n,k;char s[250000];int New_state(int _maxlen,int *_trans,int _suflink){    ++Nodecnt;    maxlen[Nodecnt]=_maxlen;    if(_trans)        for(int i=0;i<26;i++)            trans[Nodecnt][i]=_trans[i];    suflink[Nodecnt]=_suflink;    return Nodecnt;}int add_len(int u,int c){    if(trans[u][c]){        int v=trans[u][c];        if(maxlen[v]==maxlen[u]+1){            return v;        }        int y=New_state(maxlen[u]+1,trans[v],suflink[v]);        suflink[v]=y;        while(u&&trans[u][c]==v){            trans[u][c]=y;            u=suflink[u];        }        return y;    }    else{        int z=New_state(maxlen[u]+1,NULL,0);        while(u&&trans[u][c]==0){            trans[u][c]=z;            u=suflink[u];        }        if(!u){            suflink[z]=1;            return z;        }        int v=trans[u][c];        if(maxlen[v]==maxlen[u]+1){            suflink[z]=v;            return z;        }        int y=New_state(maxlen[u]+1,trans[v],suflink[v]);        suflink[z]=suflink[v]=y;        while(u&&trans[u][c]==v){            trans[u][c]=y;            u=suflink[u];        }        return z;     }}int in[250000],use[250000],v[250000],nxt[250000],fir[250000],cnt,dp[250000];void init(void){    Nodecnt=1;    memset(trans,0,sizeof(trans));    memset(suflink,0,sizeof(suflink));    memset(maxlen,0,sizeof(maxlen));    memset(in,0,sizeof(in));    memset(use,0,sizeof(use));    cnt=0;    memset(v,0,sizeof(v));    memset(nxt,0,sizeof(nxt));    memset(fir,0,sizeof(fir));    memset(dp,0,sizeof(dp));}void addedge(int ui,int vi){    ++cnt;    v[cnt]=vi;    nxt[cnt]=fir[ui];    fir[ui]=cnt;}void dfs(int u){    if(use[u]){        for(int i=0;i<26;i++){            if(trans[u][i]&&use[trans[u][i]])                in[trans[u][i]]++;            else{                int p=u;                while(p&&(trans[p][i]==0||maxlen[p]+1

q;int topu(void){ while(!q.empty()) q.pop(); for(int i=1;i<=Nodecnt;i++) use[i]=(maxlen[i]>=k),addedge(suflink[i],i); dfs(1); int num=0; for(int i=1;i<=Nodecnt;i++){ num+=use[i]; if(use[i]&&(!in[i])) q.push(i),dp[i]=maxlen[i]; } if(!num) return k-1; if(q.empty()) return 0x3f3f3f3f; while(!q.empty()){ int x=q.front(); q.pop(); for(int i=0;i<26;i++){ if(trans[x][i]){ dp[trans[x][i]]=max(dp[trans[x][i]],dp[x]+1); in[trans[x][i]]--; if(!in[trans[x][i]]) q.push(trans[x][i]); } } } int ans=0; for(int i=1;i<=Nodecnt;i++) if(use[i]&&in[i]) return 0x3f3f3f3f; else ans=max(ans,dp[i]); return ans;}int main(){ while(scanf("%d %d",&n,&k)==2){ init(); for(int i=1;i<=n;i++){ scanf("%s",s+1); int len=strlen(s+1),last=1; for(int j=1;j<=len;j++) last=add_len(last,s[j]-'a'); } int t=topu(); if(t==0x3f3f3f3f){ printf("INF\n"); } else{ printf("%d\n",t); } } return 0;}

转载于:https://www.cnblogs.com/dreagonm/p/10751207.html

你可能感兴趣的文章