Simpsons’ Hidden Talents
Problem Description
Write a program that, when given strings s1 and s2, finds the longest prefix of s1 that is a suffix of s2.
Sample Input
clinton homer
riemann marjorie
Sample Output
rie 3
思路:要求的是s1的最长前缀是s2的后缀；那么kmp中的getfail()就是用前缀来的匹配以当前点为尾点的子串的。那么如果我们 s1 += s2;那么所谓的s2的子串，就是len的匹配在s1长度总的f[i];
理解f[i]:当你那i+1的f[i+1]时，这是匹配的就是T[i] = p[i]了；
坑点:当 |s1| < |s2|时，f[i] <= |s2| ; 还有就是TLE有时不是太慢了。。而是空间炸了。。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N = ;
char T[N<<],p[N];
int f[N<<];
void getfail(char* p)
{
f[] = f[] = ;
int n = strlen(p);
for(int i = ;i < n;i++){
int j = f[i];
if(j && p[i] != p[j]) j = f[j];
f[i+] = (p[i] == p[j] ?j+:);// ｉ＋１会递推到第ｎ位
}
}
int main()
{
while(scanf("%s%s",T,p) == ){
int n = strlen(T),m = strlen(p),ans = ;
strcat(T,p);
getfail(T);
for(int j = n+m;j >= n || j >= m;j = f[j]){// n+m的f[]就是匹配后缀
//cout<<f[j]<<" ";
if(f[j] <= n && f[j] <= m){
ans = f[j];
break;
}
}
if(ans) for(int i = ;i < ans;i++) putchar(T[i]);
if(ans) putchar(' ');
printf("%d\n",ans);
}
}