The shortest common superstring of 2 strings S 1 and S 2 is a string S with the minimum number of characters which contains both S 1 and S 2 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.
Given two strings composed of lowercase English characters, find the length of their shortest common superstring.
InputThe 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 S 1 and the second line contains the string S 2. Both of these strings contain at least 1 and at most 1.000.000 characters.
OutputFor 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
这道题让我对kmp又有了更深的理解，之前对a,b串之间的字符匹配的过程还有些模糊。
本体题意：求包含a，b两字符串的最小字符串的长度。
解题思路：a，b两字符串互相进行两次kmp，满足以下三个条件：
a的后缀与b的前缀重合
a的前缀与b的后缀重合
a在b内或b在a内
则记录此时nex数组的位置，并跳出循环，具体看代码：
#include <cstdio>
#include <cstring>
const int M = 1111111;
char st[M],str[M];
int nex[M],la,lb;
void getn(char *st){
int j=-1;
nex[0]=-1;
int le=strlen(st);
for(int i=1;i<le;i++){
while(j>-1&&st[j+1]!=st[i]) j=nex[j];
if(st[j+1]==st[i]) j++;
nex[i]=j;
}
}
int kmp(char *st,char *str){
getn(st);
int j=-1;
int le=strlen(st),len=strlen(str);
for(int i=0;i<len;i++){
while(j>-1&&st[j+1]!=str[i]) j=nex[j];
if(st[j+1]==str[i]) j++;
if(j==le-1) return j; //中间
}
return j; //前缀后缀
}
int t;
int main(){
scanf("%d",&t);
while(t--){
scanf("%s %s",st,str);
int sum=strlen(st)+strlen(str);
memset(nex,0,sizeof(nex));
int a=kmp(st,str)+1;
memset(nex,0,sizeof(nex));
int b=kmp(str,st)+1;
// printf("%d %d
",a,b);
int maxx=(a>b)?a:b;
int ans=sum-maxx;
printf("%d
",ans);
}
return 0;
}
记录下kmp的板子：戳这里