| Time Limit: 2000MS | Memory Limit: 65536KB | 64bit IO Format: %I64d & %I64u |
Description
Input
Output
Sample Input
ababcababababcabab aaaaa
Sample Output
2 4 9 18 1 2 3 4 5
【解析】
题目大意：求字符串所有公共前后缀的长度。
kmp算法
【code】
#include<iostream> #include<cstdio> #include<cstring> using namespace std; #define N 400009 char s[N]; int next[N],ans[N]; int l,cnt; void getnext() { l=strlen(s); next[0]=-1; for(int i=1,j;i<l;i++) { j=next[i-1]; while(s[i]!=s[j+1]&&j>=0) j=next[j]; next[i]=s[i]==s[j+1]?j+1:-1; } } int main() { while(scanf("%s",s)!=EOF) { getnext(); cnt=0; int ll=l-1; cout<<l<<endl; cout<<next[l]<<" "<<next[ll]<<endl; while(next[ll]!=-1) { ans[++cnt]=next[ll]; ll=next[ll]; } for(int i=cnt;i>=1;i--) printf("%d ",ans[i]+1); printf("%d\n",l); } return 0; }
poj 2752 Seek the Name, Seek the Fame
原文：https://www.cnblogs.com/zzyh/p/6853621.html