https://vjudge.net/problem/SPOJ-LCS2 SPOJ注册看不到验证码,气到暴毙,用vjudge写的。
注意!(对拍的时候发现)这份代码没有对只有一个字符串的情况进行处理!所以说不定哪一天就wa了!为什么我不改呢?(因为我懒)
多个串的最长公共子串,每次匹配某个状态找到的最大值取最小值,最后再把所有状态的值取一个最大值就可以了,因为涉及到在状态上值的储存所以要按照len从大到小排序。
这次ac自动机写的很棒没有出错但是
这个地方之前写错了,果然还是太蠢了。。记一下吧
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 #include<cmath> 6 #include<map> 7 using namespace std; 8 const int maxn=100010; 9 char ch1[maxn]={},ch2[maxn]={}; 10 int siz1,siz2; 11 struct nod{ 12 int sig[26]; 13 int f,len; 14 }t[maxn*2];int tot=1,la=1; 15 int cnt[maxn*2]={}; 16 int b[maxn*2]={}; 17 int now[maxn*2]={}; 18 int mx[maxn*2]={}; 19 void add(int z){ 20 int x=++tot;int i=la; 21 t[x].len=t[la].len+1; 22 for(;i&&!t[i].sig[z];i=t[i].f) 23 t[i].sig[z]=x; 24 if(!i)t[x].f=1; 25 else{ 26 int p=t[i].sig[z]; 27 if(t[p].len==t[i].len+1)t[x].f=p; 28 else{ 29 int y=++tot; 30 t[y]=t[p];t[y].len=t[i].len+1; 31 t[x].f=t[p].f=y; 32 for(;i&&t[i].sig[z]==p;i=t[i].f){ 33 t[i].sig[z]=y; 34 } 35 } 36 } 37 la=x; 38 } 39 void pai(){ 40 for(int i=1;i<=tot;i++)cnt[t[i].len]++; 41 for(int i=0;i<=siz1;i++)if(i)cnt[i]+=cnt[i-1]; 42 for(int i=tot;i;i--)b[cnt[t[i].len]--]=i; 43 } 44 int main(){ 45 //freopen("a.in","r",stdin); 46 memset(t,0,sizeof(t)); 47 scanf("%s",ch1+1);siz1=strlen(ch1+1); 48 for(int i=1;i<=siz1;i++)add(int(ch1[i]-'a')); 49 pai(); 50 memset(mx,63,sizeof(mx)); 51 while(~scanf("%s",ch2+1)){ 52 siz2=strlen(ch2+1); 53 int j=1,tmp=0; 54 memset(now,0,sizeof(now)); 55 for(int i=1;i<=siz2;i++){ 56 int z=ch2[i]-'a'; 57 if(t[j].sig[z]){j=t[j].sig[z];tmp++;} 58 else{ 59 while(j&&!t[j].sig[z]) 60 j=t[j].f; 61 if(!j){j=1;tmp=0;} 62 else {tmp=t[j].len+1;j=t[j].sig[z];} 63 } 64 if(now[j]<tmp)now[j]=tmp; 65 } 66 for(int i=tot;i>=1;i--){ 67 int z=b[i]; 68 mx[z]=min(mx[z],now[z]); 69 if(now[z]&&t[z].f)now[t[z].f]=t[t[z].f].len; 70 } 71 } 72 int ans=0; 73 for(int i=1;i<=tot;i++)ans=max(mx[i],ans); 74 printf("%d",ans); 75 return 0; 76 }