求一个字符串的前缀与另一个字符串的后缀的最大相同子串 - 好文

求字符串ptr的前缀与str的后缀的最大相同子串，若不存在，输出0。

样例输入
mike aniom kiava dvakia dasds fdsgh
样例输出
m 1 kia 3 0
分析：

先求字符串ptr的next数组，然后使用KMP算法求ptr的前缀与str后缀的最大相同子串
#include<cstdio> #include<cstring> using namespace std; const int maxn=1e5+10;
void cal_next(char* str,int* next,int len) { next[0]=next[1]=0; for(int
i=1;i<len;++i) { int j=next[i]; while(j&&str[i]!=str[j]) j=next[j];
next[i+1]=(str[j]==str[i])?j+1:0; } } int kmp(char *str,int slen,char *ptr,int
plen) { //int *next=new int[plen]; int next[maxn]; cal_next(ptr,next,plen); /*
for(int i=0;i<plen;i++) printf("%d ",next[i]); printf("\n"); */ int j=0;
for(int i=0;i<slen;i++) { while(j&&ptr[j]!=str[i]) j=next[j];
if(ptr[j]==str[i]) ++j; } //printf("j:%d\n",j); return j; } char
str[maxn],ptr[maxn],ans[maxn]; int main() { while(scanf("%s%s",ptr,str)!=EOF){
int plen=strlen(ptr),slen=strlen(str); int len=kmp(str,slen,ptr,plen);
//printf("len:%d\n",len); if(len==0) printf("0\n"); else{
memset(ans,0,sizeof(ans)); memcpy(ans,ptr,len*sizeof (char)); printf("%s
%d\n",ans,len); } } return 0; }

热门工具换一换