Generally speaking, there are a lot of problems about strings processing. Now you encounter another such problem. If you get two strings, such as “asdf” and “sdfg”, the result of the addition between them is “asdfg”, for “sdf” is the tail substring of “asdf” and the head substring of the “sdfg” . However, the result comes as “asdfghjk”, when you have to add “asdf” and “ghjk” and guarantee the shortest string first, then the minimum lexicographic second, the same rules for other additions.
InputFor each case, there are two strings (the chars selected just form ‘a’ to ‘z’) for you, and each length of theirs won’t exceed 10^5 and won’t be empty.OutputPrint the ultimate string by the book.Sample Input
asdf sdfg asdf ghjkSample Output
asdfg asdfghjk
合并字符串，两串a，b，a的后缀和b的前缀最大匹配长度为d，b的后缀和a的前缀的最大匹配长度为e，哪个长度大，就怎么衔接，否则按字母顺序衔接。
kmp找两个长度。
代码：
#include <stdio.h> #include <string.h> #define MAX 100005 char a[MAX],b[MAX]; int Next[MAX]; void getNext(int n,char *s) { int i = 0,j = -1; Next[i] = -1; while(i < n) { if(j == -1 || s[j] == s[i]) { Next[++ i] = ++ j; } else j = Next[j]; } } int kmp(char *p,char *q) { int n = strlen(p),m = strlen(q); getNext(m,q); int i = -1,j = -1; while(i < n) { if(j == -1 || p[i] == q[j]) { i ++;j ++; } else j = Next[j]; } return j; } int main() { while(~scanf("%s%s",a,b)) { int d = kmp(a,b),e = kmp(b,a);///保存a后缀和b前缀的最大重叠 以及 反过来 比较哪个大 就重叠那个 按相应顺序输出，如果相等就按字典序 if(d > e) printf("%s%s",a,b + d); else if(d < e) printf("%s%s",b,a + e); else { if(strcmp(a,b) > 0)printf("%s%s",b,a + e); else printf("%s%s",a,b + d); } putchar(' '); } }
也可以组合求Next。
代码：
#include <iostream> #include <cstdio> #include <cstring> #define MAX 100005 using namespace std; char a[MAX],b[MAX],s[MAX * 2]; int Next[MAX * 2],m; int getNext(char *p,char *q) { strcpy(s,p); strcat(s,q); int i = 0,j = -1; Next[i] = -1; while(s[i]) { if(j == -1 || s[j] == s[i]) { Next[++ i] = ++ j; } else j = Next[j]; } int c = strlen(s); while(Next[c] > m) c = Next[c]; return Next[c]; } int main() { while(~scanf("%s%s",a,b)) { m = min(strlen(a),strlen(b)); int d = getNext(b,a),e = getNext(a,b);///保存a后缀和b前缀的最大重叠 以及 反过来 比较哪个大 就重叠那个 按相应顺序输出，如果相等就按字典序 if(d > e) printf("%s%s",a,b + d); else if(d < e) printf("%s%s",b,a + e); else { if(strcmp(a,b) > 0)printf("%s%s",b,a + e); else printf("%s%s",a,b + d); } putchar(' '); } }
当然 也可以用扩展kmp
代码：
#include <iostream> #include <cstdio> #include <cstring> #define MAX 100005 using namespace std; char a[MAX],b[MAX]; int Next[MAX],Prefix[MAX]; void getNext(char *str) {///获得Next数组 int p = 1;///匹配最远的开始匹配位置 比如从i开始和0位置依次往后匹配相等能到最远的位置 p就是i 即i + Next[i] - 1最大时的i为p Next[0] = strlen(str);///显然自己和自己匹配 Next[1] = 0; while(str[Next[1] + 1] && str[Next[1] + 1] == str[Next[1]]) Next[1] ++;///匹配1位置作为基础 for(int i = 2;str[i];i ++) {///2位置开始 if(i + Next[i - p] < p + Next[p]) Next[i] = Next[i - p];///如果不超过最远位置 else {///超过最远位置 if(p + Next[p] - 1 >= i) Next[i] = p + Next[p] - i;///i点没超过最远位置 实际是 p + Next[p] - 1 - i + 1 else Next[i] = 0;///否则从头开始匹配啊 while(str[Next[i] + i] && str[Next[i]] == str[Next[i] + i]) Next[i] ++;///继续匹配 p = i; } } } int ExKmp(char *str1,char *str2) { getNext(str2); int p = 0,len = strlen(str1); Prefix[0] = 0; while(str1[Prefix[0]] && str2[Prefix[0]] && str1[Prefix[0]] == str2[Prefix[0]]) Prefix[0] ++; for(int i = 1;str1[i];i ++) { if(i + Next[i - p] < p + Prefix[p]) Prefix[i] = Next[i - p];///i加上i-p前缀长度 没超过最远位置 else { if(i <= p + Prefix[p] - 1) Prefix[i] = p + Prefix[p] - i;///i没超过最远位置 else Prefix[i] = 0; while(str1[i + Prefix[i]] && str1[i + Prefix[i]] == str2[Prefix[i]]) Prefix[i] ++;///继续匹配 p = i;///更新最远位置下标 } } for(int i = 0;i < len;i ++) { if(i + Prefix[i] == len) return Prefix[i]; } return 0; } int main() { while(~scanf("%s%s",a,b)) { int d = ExKmp(a,b),e = ExKmp(b,a);///保存a后缀和b前缀的最大重叠 以及 反过来 比较哪个大 就重叠那个 按相应顺序输出，如果相等就按字典序 if(d > e) printf("%s%s",a,b + d); else if(d < e) printf("%s%s",b,a + e); else { if(strcmp(a,b) > 0)printf("%s%s",b,a + e); else printf("%s%s",a,b + d); } putchar(' '); } }
再次复习扩展kmp
#include <iostream> #include <cstdio> #include <cstring> #define MAX 100005 using namespace std; void getNext(char *str,int *Next) { int p = 1; while(str[1 + Next[1]] && str[1 + Next[1]] == str[Next[1]]) Next[1] ++; for(int i = 2;str[i];i ++) { if(i + Next[i - p] < p + Next[p]) Next[i] = Next[i - p]; else { if(i <= p + Next[p] - 1) Next[i] = p + Next[p] - i; else Next[i] = 0; while(str[i + Next[i]] && str[i + Next[i]] == str[Next[i]]) Next[i] ++; p = i; } } } int ExKmp(char *s,char *t) { int Next[MAX] = {0},Prefix[MAX] = {0}; getNext(t,Next); int p = 0; while(s[0 + Prefix[0]] && s[0 + Prefix[0]] == t[Prefix[0]]) Prefix[0] ++; for(int i = 1;s[i];i ++) { if(i + Next[i - p] < p + Prefix[p]) Prefix[i] = Next[i - p]; else { if(i < p + Prefix[p]) Prefix[i] = p + Prefix[p] - i; else Prefix[i] = 0; while(s[i + Prefix[i]] && s[i + Prefix[i]] == t[Prefix[i]]) Prefix[i] ++; if(i + Prefix[i] > p + Prefix[p]) p = i;///不加这一步 最后返回的就不对， 比如 aaaa aaa 应输出 aaaa } } return p + Prefix[p] < strlen(s) ? 0 : Prefix[p]; } int main() { char a[MAX],b[MAX]; while(~scanf("%s%s",a,b)) { int d = ExKmp(a,b),e = ExKmp(b,a); if(d > e) printf("%s%s",a,b + d); else if(d < e) printf("%s%s",b,a + e); else { if(strcmp(a,b) > 0)printf("%s%s",b,a + e); else printf("%s%s",a,b + d); } putchar(' '); } }