题意：找出一个最大的公共子串，这个子串是一个字符串的尾串（tail substring ），同时是另外那个字符串的头串（head substring），是满足A+B的长度strlen(A+B)达到最小值，这里面要注意的一个问题是，谁做模式串P是不一定的，所以要分别比较不同字符串作为模式的KMP值。
思路：让两个串分别做模式串。看谁KMP的结束的时候匹配的字符字符的个数最多就好。
当然也可以把两个串连接起来再求一次next[len1+len2]即可（求next相当于自我匹配），这时候要注意ans=next[len1+len2]可能大于其中的任何一串，那么就迭代直到(ans=next[ans])<min(len1,len2)，，因为这个wa了一次
方法一：//2084 KB46 ms#include<cstdio>#include<iostream>#include<cstring>#include<algorithm>using namespace std;char a[100100],b[100100];char s1[200200],s2[200200];int next1[200200],next2[200200];int combine(char a[],char b[],char s[]){bool flag=0;int len,j;for(len=0,j=0;;len++,j++){if(a[j]==0){if(flag) break;flag=1;a=b;j=0;}s[len]=a[j];}s[len]=0;return len;}void getnext(char str[],int next[]){int i=0;int j=next[0]=-1;while(str[i]!=0){while(j>-1&&str[i]!=str[j])j=next[j];i++;j++;next[i]=j;}}int kmp(int next[],char fa[],char son[]){int i=0,j=0;int len1=strlen(fa),len2=strlen(son);while(i<len1&&j<len2){if(j==-1||fa[i]==son[j]){j++;i++;}else j=next[j];}return fa[i]==0? j:0;}int main(){while(~scanf("%s%s",a,b)){getnext(a,next1);getnext(b,next2);int cut1=kmp(next2,a,b);int cut2=kmp(next1,b,a);if(cut1==cut2){if(strcmp(a,b)<0) printf("%s%s\n",a,b+cut1);else printf("%s%s\n",b,a+cut2);}else{if(cut1>cut2) printf("%s%s\n",a,b+cut1);else printf("%s%s\n",b,a+cut2);}}return 0;}
方法二：
贴上大仙的代码:
/************************************************************************* > File Name: 1867.cpp > Author: UnknownCUnknown > Mail: jsnjhcb@icloud.com > Created Time: 2015年02月12日 星期四 16时17分07秒 ************************************************************************/#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cctype>#include <vector>#include <map>#include <set>#include <stack>#include <list>#include <string>#include <cstdlib>#include <queue>#include <cmath>#include <climits>using namespace std;const int maxn=1e5;char s1[maxn+10],s2[maxn+10];char s[2*maxn+10];int next[2*maxn+10];int len;void getNext(){len=(int)strlen(s);int j,k;j=0;k=-1;next[0]=-1;while(j<len){if(k==-1||s[j]==s[k]) next[++j]=++k;else k=next[k];}}char ans[2*maxn+10];char ans1[2*maxn+10];int main(){while(~scanf("%s%s",s1,s2)){int l1=(int) strlen(s1);int l2=(int) strlen(s2);int l=min(l1,l2);strcpy(s,s2);strcat(s,s1);getNext();int k1=next[len];while(k1>l){k1=next[k1];}strcpy(s,s1);strcat(s,s2);getNext();int k=next[len];while(k>l) k=next[k];if (k>k1){strcpy(ans,s2);strcat(ans,s1+k);}else if(k<k1){strcpy(ans,s1);strcat(ans,s2+k1);}else {strcpy(ans,s2);strcat(ans,s1+k);strcpy(ans1,s1);strcat(ans1,s2+k1);if(strcmp(ans1,ans)<0){strcpy(ans,ans1);}}printf("%s\n",ans);}return 0;}
正确的寒暄必须在短短一句话中明显地表露出你对他的关怀。
