【贪心】【后缀自动机】XIII Open Championship of Y.Kupala Grodno SU Grodno, Saturday, April 29, 2017 Problem E. Enter the Word

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题意：给你一个串，让你从左到右构造这个串，一次操作可以直接在当前串后面添加一个任意字符，或者拷贝当前串的任意一个子串到当前串的后面。问你最少要多少次操作才能构造出这个串。

从前向后贪心，从当前已构造的串的后面开始，尽量往后走，尝试在后缀自动机上转移，直到不能转移为止，便求出了后面的串的在当前串中能找到的最长前缀是多少，然后答案++，然后把这个最长前缀加入后缀自动机接着跑即可。不会证明。

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define MAXL 200000

#define MAXC 26

int v[2*MAXL+10],__next[2*MAXL+10],first[2*MAXL+10],e;

void AddEdge(int U,int V){

    v[++e]=V;

    __next[e]=first[U];

    first[U]=e;

}

char s[MAXL+10];

int len;

struct SAM{

    int endcnt[2*MAXL+10];

    int n,maxlen[2*MAXL+10],minlen[2*MAXL+10],trans[2*MAXL+10][MAXC],slink[2*MAXL+10];

    void clear(){

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

            endcnt[i]=maxlen[i]=minlen[i]=slink[i]=first[i]=0;

            memset(trans[i],0,sizeof(trans[i]));

        }

        n=e=0;

    }

    int new_state(int _maxlen,int _minlen,int _trans[],int _slink){

        maxlen[n]=_maxlen;

        minlen[n]=_minlen;

        for(int i=0;i<MAXC;++i){

            if(_trans==NULL){

                trans[n][i]=-1;

            }

            else{

                trans[n][i]=_trans[i];

            }

        }

        slink[n]=_slink;

        return n++;

    }

    int add_char(char ch,int u){

        if(u==-1){

            return new_state(0,0,NULL,-1);

        }

        int c=ch-'a';

        int z=new_state(maxlen[u]+1,-1,NULL,-1);

        endcnt[z]=1;

        int v=u;

        while(v!=-1 && trans[v][c]==-1){

            trans[v][c]=z;

            v=slink[v];

        }

        if(v==-1){

            minlen[z]=1;

            slink[z]=0;

            return z;

        }

        int x=trans[v][c];

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

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

            slink[z]=x;

            return z;

        }

        int y=new_state(maxlen[v]+1,-1,trans[x],slink[x]);

        slink[y]=slink[x];

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

        slink[x]=y;

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

        slink[z]=y;

        int w=v;

        while(w!=-1 && trans[w][c]==x){

            trans[w][c]=y;

            w=slink[w];

        }

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

        return z;

    }

}sam;

int ans;

int main(){

//	freopen("e.in","r",stdin);

	scanf("%s",s);

    len=strlen(s);

    int U=sam.add_char(0,-1);

    int i=0;

    while(i<len){

    	if(sam.trans[0][s[i]-'a']==-1){

    		U=sam.add_char(s[i],U);

    		++i;

    	}

    	else{

    		int j=i,V=0;

    		while(V!=-1 && j<len){

    			V=sam.trans[V][s[j]-'a'];

   	 			++j;

    		}

    		if(j==len && V!=-1){

    			++ans;

    			break;

    		}

    		for(int k=i;k<j-1;++k){

    			U=sam.add_char(s[k],U);

    		}

    		i=j-1;

    	}

    	++ans;

    }

    printf("%d\n",ans);

    return 0;

}