题意：给两个字符串，问包含这两个字符串的最小的字符串的长度
kmp返回匹配串长度
#include "iostream" #include<cstdio> #include<algorithm> #include<cstring> using namespace std; #define N 1000005 char s[N],t[N]; int next1[N]; void get_next(char b[]) { next1[0]=-1; int i=0; int j=-1; int str=strlen(b); while(i<str-1) { if(j==-1||b[i]==b[j]) next1[++i]=++j; else j=next1[j]; } } int kmp(char a[],char b[],int stra,int strb) { int i=0; int j=-1; get_next(b);///b为模式串 while(i<stra&&j<strb) { if(j==-1||a[i]==b[j]) i++,j++; else j=next1[j]; } return j; } int main() { int i,j,n,ans,cnt,ls,lt; scanf("%d",&n); while(n--) { scanf("%s%s",s,t); ls=strlen(s); lt=strlen(t); ans=kmp(s,t,ls,lt); cnt=kmp(t,s,lt,ls); printf("%d\n",ls+lt-max(ans,cnt)); } return 0; }