居然要用到kmp…
瞎搞了半天…不对是四个月,今天无意中翻到这题还是不会做,抄了下题解
首先这个kmp的匹配就稍微变形了一点,用kmp(a,b)然后不是输出匹配的位置,也不是输出匹配的数量,而是输入当i==sl的时候,也就是原串匹配完了,这时候pat匹配到那个位置,输入j,这样把a和b分别作为模式串去匹配另一个,看看谁的前缀能连上另一个的后缀的长度更长一些,如果相同再比较字典序
代码:
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
const int N=200050;
int Next[N];
char a[N];
char b[N];
char t[N];
void getNext(char* s){
memset(Next,0,sizeof(Next));
int i=0;
int j=-1;
Next[0]=-1;
int l=strlen(s);
while(i<l){
if(j==-1 || s[i]==s[j]){
Next[++i]=++j;
}
else{
j=Next[j];
}
}
}
int kmp(char *str,char *pat){
memset(Next,0,sizeof(Next));
getNext(pat);
int i=0,j=0;
int sl=strlen(str);
int pl=strlen(pat);
while(i<sl && j<pl){
if(j==-1 || str[i]==pat[j]){
i++;
j++;
}
else{
j=Next[j];
}
}
if(i==sl){
return j;
}
else{
return -1;
}
}
int main(void){
while(~scanf("%s %s",a,b)){
int t1=kmp(a,b);
int t2=kmp(b,a);
if(t1>t2){
printf("%s",a);
printf("%s\n",&b[t1]);
}
else if(t1<t2){
printf("%s",b);
printf("%s\n",&a[t2]);
}
else{
if(strcmp(a,b)<0){
printf("%s%s\n",a,&b[t1]);
}
else{
printf("%s%s\n",b,&a[t2]);
}
}
}
return 0;
}