Sample Input
clinton homer riemann marjorie
Sample Output
0 rie 3
看输出才题意。。。
拓展kmp特征很明显嘛。。。。
注意开始就匹配到尾的情况
#include <iostream> #include <cstdio> #include <sstream> #include <cstring> #include <map> #include <set> #include <vector> #include <stack> #include <queue> #include <algorithm> #include <cmath> #define rap(i, a, n) for(int i=a; i<=n; i++) #define rep(i, a, n) for(int i=a; i<n; i++) #define lap(i, a, n) for(int i=n; i>=a; i--) #define lep(i, a, n) for(int i=n; i>a; i--) #define rd(a) scanf("%d", &a) #define rlld(a) scanf("%lld", &a) #define rc(a) scanf("%c", &a) #define rs(a) scanf("%s", a) #define MOD 2018 #define LL long long #define ULL unsigned long long #define Pair pair<int, int> #define mem(a, b) memset(a, b, sizeof(a)) #define _ ios_base::sync_with_stdio(0),cin.tie(0) //freopen("1.txt", "r", stdin); using namespace std; const int maxn = 50010, INF = 0x7fffffff; int nex[maxn], ex[maxn]; void get_next(char *s) { int i=0, j, po, len = strlen(s); nex[0] = len; while(i+1 < len && s[i] == s[i+1]) i++; nex[1] = i; po = 1; for(int i=2; i<len; i++) { if(i+nex[i-po] < po + nex[po]) nex[i] = nex[i-po]; else { j = po + nex[po] - i; if(j < 0) j = 0; while(i + j < len && s[i+j] == s[j]) j++; nex[i] = j; po = i; } } } int get_ex(char *s1, char *s2) { int i=0, j, po, len1 = strlen(s1), len2 = strlen(s2); get_next(s2); while(s1[i] == s2[i] && i < len1 && i < len2) i++; ex[0] = i; if(i == len1) return 1; po = 0; for(int i=1; i<len1; i++) { if(i + nex[i - po] < po + ex[po]) ex[i] = nex[i-po]; else { j = po + ex[po] - i; if(j < 0) j = 0; while(i + j < len1 && j < len2 && s1[i+j] == s2[j]) j++; ex[i] = j; po = i; if(ex[i] == len1 - i) return i + 1; } } return 0; } char s1[maxn], s2[maxn]; int main() { while(~rs(s1)) { rs(s2); int flag = get_ex(s2, s1); int len = strlen(s2); if(flag) { rep(i, flag-1, len) cout<<s2[i]; cout<<" "; cout<< ex[flag-1] <<endl; } else cout<< "0" <<endl; } return 0; }