学步园

Description

Input

Output

Sample Input

yeshowmuchiloveyoumydearmotherreallyicannotbelieveit
yeaphowmuchiloveyoumydearmother

Sample Output

27

Source

#include<iostream><br /> #include<cstdio><br /> #include<cstring><br /> using namespace std;<br /> const int maxn=500000;<br /> char str[maxn];<br /> int wa[maxn],wb[maxn],wv[maxn],wn[maxn],a[maxn],sa[maxn];<br /> int cmp(int* r,int a,int b,int l)<br /> {<br /> return r[a]==r[b]&&r[a+l]==r[b+l];<br /> }<br /> //n为字符串长度，m为字符的取值范围，r为字符串。后面的j为每次排序时子串的长度<br /> void DA(int* r,int* sa,int n,int m)<br /> {<br /> int i,j,p,*x=wa,*y=wb,*t;<br /> ///对R中长度为1的子串进行基数排序<br /> for(i=0; i<m; i++)wn[i]=0;<br /> for(i=0; i<n; i++)wn[x[i]=r[i]]++;<br /> for(i=1; i<m; i++)wn[i]+=wn[i-1];<br /> for(i=n-1; i>=0; i--)sa[--wn[x[i]]]=i;<br /> for(j=1,p=1; p<n; j*=2,m=p)<br /> {<br /> //利用了上一次基数排序的结果，对待排序的子串的第二关键字进行了一次高效地基数排序<br /> for(p=0,i=n-j; i<n; i++)y[p++]=i;<br /> for(i=0; i<n; i++)if(sa[i]>=j)y[p++]=sa[i]-j;<br /> ///基数排序<br /> for(i=0; i<n; i++)wv[i]=x[y[i]];<br /> for(i=0; i<m; i++)wn[i]=0;<br /> for(i=0; i<n; i++)wn[wv[i]]++;<br /> for(i=1; i<m; i++)wn[i]+=wn[i-1];<br /> for(i=n-1; i>=0; i--)sa[--wn[wv[i]]]=y[i];<br /> ///当p=n的时候，说明所有串都已经排好序了<br /> ///在第一次排序以后，rank数组中的最大值小于p，所以让m=p<br /> for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1; i<n; i++)<br /> x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;<br /> }<br /> return;<br /> }<br /> ///后缀数组 计算height数组<br /> /**<br /> height数组的值应该是从height[1]开始的，而且height[1]应该是等于0的。<br /> 原因是，+因为我们在字符串后面添加了一个0号字符，所以它必然是最小的<br /> 一个后缀。而字符串中的其他字符都应该是大于0的（前面有提到，使用倍<br /> 增<span class='wp_keywordlink'><a href="http://www.xuebuyuan.com/category/%E7%AE%97%E6%B3%95" title="算法" target="_blank">算法</a></span>前需要确保这点），所以排名第二的字符串和0号字符的公共前缀<br /> （即height[1]）应当为0.在调用calheight函数时，要注意height数组的范<br /> 围应该是[1..n]。所以调用时应该是calheight(r,sa,n)<br /> 而不是calheight(r,sa,n+1)。*/<br /> int rank[maxn],height[maxn];<br /> void calheight(int* r,int* sa,int n)<br /> {<br /> int i,j,k=0;<br /> for(i=1; i<=n; i++)rank[sa[i]]=i;<br /> for(i=0; i<n; height[rank[i++]]=k)<br /> for(k?k--:0,j=sa[rank[i]-1]; r[i+k]==r[j+k]; k++);<br /> return;<br /> }<br /> //最长公共子串<br /> bool check(int a,int b,int n1,int n2)<br /> {<br /> if(a>b) return check(b,a,n1,n2);<br /> if(a<n1&&b>n1) return 1;<br /> return 0;<br /> }<br /> int main()<br /> {<br /> //后缀数组 倍增算法 使用方法<br /> /**<br /> 在使用倍增算法前，需要保证r数组的值均大于0。然后要在原字<br /> 符串后添加一个0号字符，具体原因参见罗穗骞的论文。这时候，<br /> 若原串的长度为n，则实际要进行后缀数组构建的r数组的长度应<br /> 该为n+1.所以调用DA函数时，对应的n应为n+1.*/<br /> /* int n=strlen(str);//str 待处理字符串<br /> for(int i=0;i<n;i++) a[i]=(int)str[i];<br /> a[n]=0;<br /> DA(a,sa,n+1,256);<br /> calheight(a,sa,n);*/<br /> //....................................<br /> char str1[maxn],str2[maxn];<br /> scanf("%s%s",str1,str2);<br /> int n1=strlen(str1),n2=strlen(str2);<br /> for(int i=0; i<n1; i++) a[i]=(int)str1[i];<br /> a[n1]=24;//notice 1<br /> for(int i=0; i<n2; i++) a[n1+1+i]=(int)str2[i];<br /> a[n1+1+n2+1]=24;<br /> int n=n1+n2+1;<br /> DA(a,sa,n+1,256);<br /> calheight(a,sa,n);<br /> /**1. 求两个字符串的最长公共子串<br /> 先将第二个字符串写在第一个字符串后面，中间用一个没有出现过<br /> 的字符隔开，再求这个新的字符串的后缀数组。观察一下，看看能<br /> 不能从这个新的字符串的后缀数组中找到一些规律。以A=“aaaba”，<br /> B=“abaa”为例,那么是不是所有的height值中的最大值就是答案呢？<br /> 不一定！有可能这两个后缀是在同一个字符串中的，所以实际上只<br /> 有当suffix(sa[i-1])和suffix(sa[i])不是同一个字符串中的两个后<br /> 缀时，height[i]才是满足条件的。而这其中的最大值就是答案<br /> */<br /> int rmax=0;<br /> for(int i=1; i<=n; i++)<br /> {<br /> if(((sa[i]<n1&&sa[i-1]>n1)||(sa[i]>n1&&sa[i-1]<n1))&&height[i]>rmax)<br /> rmax=height[i];<br /> }<br /> printf("%d/n",rmax);<br /> return 0;<br /> }<br />