题意:
给你一个串T,找出串T的子串,该串既是T的前缀也是T的后缀。从小到大输出所有符合要求的串的长度。
分析:
首先要知道KMP的next[i]数组求得的数值就是串T中的[1,i-1]的后缀与串T中的[0,i-2]前缀的最大匹配长度。 所以next[m](m为串长且串从0到m-1下标)的值就是与后缀匹配的最大前缀长度(想想是不是)。
next[next[m]]也是一个与后缀匹配的前缀长度,,,依次类推即可。
题解来自饶齐：http://blog.csdn.net/u013480600/article/details/23024781
//作者:1085422276 #include <cstdio> #include <cmath> #include <string> #include <cstring> #include <ctime> #include <iostream> #include <algorithm> #include <set> #include <vector> #include <sstream> #include <queue> #include <typeinfo> //#include<bits/stdc++.h> #include <map> #include <stack> typedef long long ll; using namespace std; const int inf = 10000000; inline ll read() { ll x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-')f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=x*10+ch-'0'; ch=getchar(); } return x*f; } ll exgcd(ll a,ll b,ll &x,ll &y) { ll temp,p; if(b==0) { x=1; y=0; return a; } p=exgcd(b,a%b,x,y); temp=x; x=y; y=temp-(a/b)*y; return p; } //******************************* char a[400005]; int maxl[400005],p[400005]; int main() { while(gets(a)!=NULL) { int n=strlen(a); memset(p,0,sizeof(p)); int j=0; for(int i=1;i<n;i++) { while(j>0&&a[j]!=a[i])j=p[j]; if(a[j]==a[i])j++; p[i+1]=j; } int cnt=0; maxl[++cnt]=n; int i=n; while(p[n]) { maxl[++cnt]=p[n]; n=p[n]; } for(int i=cnt;i>1;i--) { printf("%d ",maxl[i]); } printf("%d ",maxl[1]); } return 0; }