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
Sample Output
題目要求2個(gè)字符串的shortest common superstring，最小公共父串：使得str1和str2都包含在所求的superstring中，且該superstring的長度最小。設(shè)str1的長度為m，str2的長度為n，如果按照逐個(gè)位置匹配求公共部分的方法，時(shí)間復(fù)雜度為O(m*n)。題目中的n∈[1,1000000]，顯然會(huì)TLE，必須降低時(shí)間復(fù)雜度，只能用KMP模式匹配算法來做了，時(shí)間復(fù)雜度O(m+n)。
用KMP算法來求解時(shí)，分3種情況：
----str1與str2能完全匹配，長度為max{len1,len2},如banana，ban；
----str1與str2不能匹配，但是能找到公共部分，如字符串a(chǎn)lba，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 }