【贪心】【后缀自动机】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
",ans);
return 0;
}