题目来源:http://poj.org/problem?id=2774
题目分类:后缀树组
此题心得:学习后缀树组
时间:2011-7-21
Long Long Message
Description The little cat is majoring in physics in the capital of Byterland. A piece of sad news comes to him these days: his mother is getting ill. Being worried about spending so much on railway tickets (Byterland is such a big country, and he has to spend 16 shours on train to his hometown), he decided only to send SMS with his mother. The little cat lives in an unrich family, so he frequently comes to the mobile service center, to check how much money he has spent on SMS. Yesterday, the computer of service center was broken, and printed two very long messages. The brilliant little cat soon found out: 1. All characters in messages are lowercase Latin letters, without punctuations and spaces. You are given those two very long messages, and you have to output the length of the longest possible original text written by the little cat. Background: Why ask you to write a program? There are four resions: Input Two strings with lowercase letters on two of the input lines individually. Number of characters in each one will never exceed 100000. Output A single line with a single integer number – what is the maximum length of the original text written by the little cat. Sample Input yeshowmuchiloveyoumydearmotherreallyicannotbelieveit yeaphowmuchiloveyoumydearmother Sample Output 27 Source POJ Monthly--2006.03.26,Zeyuan Zhu,"Dedicate to my great beloved mother." |
[Submit] [Go Back] [Status] [Discuss]
All Rights Reserved 2003-2011 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator
题意与分析
题意:给你两个字符串,求两个串的最长公共子串,数据量为10^5。
分析:对10^3的数据量,求两个串的最长公共字串是个经典的问题了。但此题数据限制很大。用后缀树组,先将两个串结合一起中间加上一个两个串都没有的值,先求出height数组,这样这个问题就转化为了求着一个串的最长公共前缀,扫描一遍height数组就可以得到答案了。但是要保证这两个前缀分别在两个串中,所以要加一个判断保证两个串首地址i<len1<j
源代码
· #include<stdio.h>
· #include<string.h>
·
·
· #define maxn 1000003
· #define F(x) ((x)/3+((x)%3==1?0:tb))
· #define G(x) ((x)<tb?(x)*3+1:((x)-tb)*3+2)
· int wa[maxn],wb[maxn],wv[maxn],ws[maxn];
· int c0(int *r,int a,int b)
· {return r[a]==r[b]&&r[a+1]==r[b+1]&&r[a+2]==r[b+2];}
· int c12(int k,int *r,int a,int b)
· {if(k==2) return r[a]<r[b]||r[a]==r[b]&&c12(1,r,a+1,b+1);
· else return r[a]<r[b]||r[a]==r[b]&&wv[a+1]<wv[b+1];}
· void sort(int *r,int *a,int *b,int n,int m)
· {
· int i;
· for(i=0;i<n;i++) wv[i]=r[a[i]];
· for(i=0;i<m;i++) ws[i]=0;
· for(i=0;i<n;i++) ws[wv[i]]++;
· for(i=1;i<m;i++) ws[i]+=ws[i-1];
· for(i=n-1;i>=0;i--) b[--ws[wv[i]]]=a[i];
· return;
· }
· void dc3(int *r,int *sa,int n,int m)
· {
· int i,j,*rn=r+n,*san=sa+n,ta=0,tb=(n+1)/3,tbc=0,p;
· r[n]=r[n+1]=0;
· for(i=0;i<n;i++) if(i%3!=0) wa[tbc++]=i;
· sort(r+2,wa,wb,tbc,m);
· sort(r+1,wb,wa,tbc,m);
· sort(r,wa,wb,tbc,m);
· for(p=1,rn[F(wb[0])]=0,i=1;i<tbc;i++)
· rn[F(wb[i])]=c0(r,wb[i-1],wb[i])?p-1:p++;
· if(p<tbc) dc3(rn,san,tbc,p);
· else for(i=0;i<tbc;i++) san[rn[i]]=i;
· for(i=0;i<tbc;i++) if(san[i]<tb) wb[ta++]=san[i]*3;
· if(n%3==1) wb[ta++]=n-1;
· sort(r,wb,wa,ta,m);
· for(i=0;i<tbc;i++) wv[wb[i]=G(san[i])]=i;
· for(i=0,j=0,p=0;i<ta && j<tbc;p++)
· sa[p]=c12(wb[j]%3,r,wa[i],wb[j])?wa[i++]:wb[j++];
· for(;i<ta;p++) sa[p]=wa[i++];
· for(;j<tbc;p++) sa[p]=wb[j++];
· return;
· }
· int rank[maxn],height[maxn];
· void calheight(int *r,int *sa,int n)
· {
· int i,j,k=0;
· for(i=1;i<=n;i++) rank[sa[i]]=i;
· for(i=0;i<n;height[rank[i++]]=k)
· for(k?k--:0,j=sa[rank[i]-1];r[i+k]==r[j+k];k++);
· return;
· }
· int RMQ[maxn];
· int mm[maxn];
· int best[20][maxn];
· void initRMQ(int n)
· {
· int i,j,a,b;
· for(mm[0]=-1,i=1;i<=n;i++)
· mm[i]=((i&(i-1))==0)?mm[i-1]+1:mm[i-1];
· for(i=1;i<=n;i++) best[0][i]=i;
· for(i=1;i<=mm[n];i++)
· for(j=1;j<=n+1-(1<<i);j++)
· {
· a=best[i-1][j];
· b=best[i-1][j+(1<<(i-1))];
· if(RMQ[a]<RMQ[b]) best[i][j]=a;
· else best[i][j]=b;
· }
· return;
· }
· int askRMQ(int a,int b)
· {
· int t;
· t=mm[b-a+1];b-=(1<<t)-1;
· a=best[t][a];b=best[t][b];
· return RMQ[a]<RMQ[b]?a:b;
· }
· int lcp(int a,int b)
· {
· int t;
· a=rank[a];b=rank[b];
· if(a>b) {t=a;a=b;b=t;}
· return(height[askRMQ(a+1,b)]);
· }
·
·
· //求两串最长公共字串示例。。。
· int len1, len2, n, mx;
· char s1[maxn], s2[maxn];
· int sa[maxn], a[maxn];
· int main()
· {
· int i;
· while(scanf("%s %s", s1, s2)!=EOF)
· {
· len1 = strlen(s1);
· len2 = strlen(s2);
· n = len1+len2;
· for(i=0; i<len1; i++)
· a[i] = s1[i] - 'a' + 1;
· a[len1] = 100;
· for(i=0; i<len2; i++)
· a[i+len1+1] = s2[i] - 'a' + 1;
· a[len1+len2+1] = 0;
· dc3(a, sa, n+2, 200);
· calheight(a, sa, n+1);
· for(i=2; i<n+2; i++)
· {
· if((sa[i]<len1 && sa[i-1]>len1)||(sa[i]>len1 && sa[i-1]<len1))
· if(mx<height[i])
· mx = height[i];
· }
· printf("%d\n", mx);
· }
· return 0;
· }