题目链接如下:http://acm.hdu.edu.cn/showproblem.php?pid=1867
题意:将两个字符串加在一起,重复的部分只出现一次,长度越短优先,字典序越短优先,
思路:kmp 求出两个字符串做为各自字串kmp值,kmp有修改;
代码:
#include<iostream> #include<stdio.h> #include<string.h> #include<algorithm> #include<vector> #include<stack> #include<queue> #include<list> #include<string> using namespace std; const int maxn=222222; int next[maxn]; void getnext(char x[]) { int i,j; int m=strlen(x); j=next[0]=-1; i=0; while(i<m) { while(j!=-1&&x[i]!=x[j])j=next[j]; next[++i]=++j; } } int kmp(char s[],char t[]) { int n=strlen(s); int m=strlen(t); getnext(t); int i,j; for(i=0,j=0;i<n&&j<m;) { if(j==-1||s[i]==t[j]) ++i,++j; else j=next[j]; } if(i>=n)return j; return 0; } int main() { char s[maxn],t[maxn]; for(; ~scanf("%s%s",s,t);) { int x=kmp(s,t); int y=kmp(t,s); if(x==y) { if(strcmp(s,t)>0) { printf("%s",t); printf("%s\n",s+x); } else { printf("%s",s); printf("%s\n",t+x); } } else if(x>y) { printf("%s",s); printf("%s\n",t+x); } else { printf("%s",t); printf("%s\n",s+y); } } return 0; }