HDOJ 1841 Find the Shortest Common Superstring (最小公共父串)

Problem Description
The shortest common superstring of 2 strings S1 and S2 is a string S with the minimum number of characters which contains both S1 and S2 as a sequence of consecutive characters. For instance, the shortest common superstring of “alba” and “bacau” is “albacau”.
Given two strings composed of lowercase English characters, find the length of their shortest common superstring.
 

Input
The first line of input contains an integer number T, representing the number of test cases to follow. Each test case consists of 2 lines. The first of these lines contains the string S1 and the second line contains the string S2. Both of these strings contain at least 1 and at most 1.000.000 characters.
 

Output
For each of the T test cases, in the order given in the input, print one line containing the length of the shortest common superstring.
 

Sample Input
2
alba
bacau
resita
mures
 

Sample Output
7
8
   题目要求2个字符串的shortest common superstring,最小公共父串:使得str1和str2都包含在所求的superstring中,且该superstring的长度最小。设str1的长度为m,str2的长度为n,如果按照逐个位置匹配求公共部分的方法,时间复杂度为O(m*n)。题目中的n∈[1,1000000],显然会TLE,必须降低时间复杂度,只能用KMP模式匹配算法来做了,时间复杂度O(m+n)。
   用KMP算法来求解时,分3种情况:
   ----str1与str2能完全匹配,长度为max{len1,len2},如banana,ban;
   ----str1与str2不能匹配,但是能找到公共部分,如字符串alba,bacau,公共部分ba长度为2;
   ----str1与str2不能匹配,且没有公共部分,如asdf,ghjk。
 1 #include <iostream>
 2 
 3 #define max(a,b) (a>b?a:b)
 4 #define match(a,b) ((a)==(b))
 5 const int MAXN = 1000001;
 6 int fail[MAXN];
 7 char str[2][MAXN];
 8 
 9 int kmp_pat_match(char *str,int ls,int &i,char *pat,int lp,int &j){
10     fail[0]=-1,i=0,j;
11     for(j=1;j<lp;j++){
12         for(i=fail[j-1];i>=0 && !match(pat[i+1],pat[j]);i=fail[i]);
13         fail[j]=match(pat[i+1],pat[j])?i+1:-1;
14     }
15     for(i=j=0;i<ls&&j<lp;i++)
16         if(match(str[i],pat[j])) j++;
17         else if(j)
18             j=fail[j-1]+1,i--;
19     return j==lp?(i-lp):-1;
20 }
21 int main(){
22     int i,j,t,u,v,len1,len2,pos;
23     scanf("%d",&t),getchar();
24     while(t--){
25         gets(str[0]),gets(str[1]);
26         len1=strlen(str[0]),len2=strlen(str[1]);
27         u=0,pos=kmp_pat_match(str[0],len1,i,str[1],len2,j);
28         if(pos!=-1) u=len2;
29         else if(i==len1 && j>0 && match(str[0][len1-1],str[1][j-1])) u=j;
30         v=0,pos=kmp_pat_match(str[1],len2,i,str[0],len1,j);
31         if(pos!=-1) v=len1;
32         else if(i==len2 && j>0 && match(str[1][len2-1],str[0][j-1])) v=j;
33         printf("%d\n",len1+len2-max(u,v));
34     }
35     return 0;
36 }

posted on 2009-04-28 13:38 极限定律 阅读(599) 评论(0)  编辑 收藏 引用 所属分类: ACM/ICPC


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2009年4月>
2930311234
567891011
12131415161718
19202122232425
262728293012
3456789

导航

统计

常用链接

留言簿(10)

随笔分类

随笔档案

友情链接

搜索

最新评论

阅读排行榜

评论排行榜