题目意思: 给出两个字符串a, b, 求最长的公共字串c, c是a的后缀,也是b的前缀. 本题没有具体说明哪个字符串是文本串和匹配串, 所以都要考虑
思路: 查找的时候, 当文本串结束的时候, 返回匹配串的位
/*************************************************************************
> File Name: 1867.cpp
> Author: Stomach_ache
> Mail: [email protected]
> Created Time: 2014年05月15日 星期四 11时24分11秒
> Propose:
************************************************************************/ #include <cmath>
#include <string>
#include <cstdio>
#include <fstream>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define MAX_N (100000+5) char a[MAX_N], b[MAX_N];
int f[MAX_N<<];
void getFail(char *); int
find (char *T, char *P) {
int n = strlen(T);//m = strlen(P);
getFail(P);
int j = ;
for (int i = ; i < n; i++) {
while (j && T[i] != P[j]) j = f[j];
if (P[j] == T[i]) j++;
} return j;
} void
getFail(char *P) {
int m = strlen(P);
f[] = f[] = ;
for (int i = ; i < m; i++) {
int j = f[i];
while (j && P[i] != P[j]) j = f[j];
f[i+] = P[i] == P[j] ? j+ : ;
}
} int
main(void) {
while (~scanf("%s %s", a, b)) {
// int len1 = strlen(a);
// int len2 = strlen(b);
int cnt = find(a, b);
// cout << cnt << endl;
int cnt2 = find(b, a);
// cout << cnt2 << endl;
if (cnt > cnt2) {
printf("%s", a);
printf("%s\n", b+cnt);
} else if (cnt < cnt2){
printf("%s", b);
printf("%s\n", a+cnt2);
} else {
if (strcmp(a, b) < ) {
printf("%s", a);
printf("%s\n", b+cnt);
} else {
printf("%s", b);
printf("%s\n", a+cnt2);
}
}
} return ;
}