题意:
给出一个字符串str,求出str中存在多少子串,使得这些子串既是str的前缀,又是str的后缀。从小到大依次输出这些子串的长度。
这个就是next数组的应用,next数组真是很深奥啊。
根据最后一个next数组的值,递归去找前面的值,直到是0时停止。证明见链接。
链接:http://www.cnblogs.com/dongsheng/archive/2012/08/13/2636261.html
#include <map> #include <set> #include <list> #include <cmath> #include <queue> #include <stack> #include <vector> #include <cstdio> #include <string> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int INF=0x3f3f3f3f; typedef long long LL; #define PI(A) printf("%d\n",A) #define SI(N) scanf("%d",&(N)) #define SII(N,M) scanf("%d%d",&(N),&(M)) #define cle(a,val) memset(a,(val),sizeof(a)) #define rep(i,b) for(int i=0;i<(b);i++) #define Rep(i,a,b) for(int i=(a);i<=(b);i++) #define reRep(i,a,b) for(int i=(a);i>=(b);i--) ; /* ///////////////////////// C o d i n g S p a c e ///////////////////////// */ + ; int nnext[MAXN]; char s[MAXN]; int sum[MAXN]; void getnext(int len) { int i,j; i=; j=-; nnext[]=-; while(i<len) { ||s[i]==s[j]) { ++i,++j; nnext[i]=j; } else { j=nnext[j]; } } } int main() { int len,i,k; while(scanf("%s",s)!=EOF) { k=; len=strlen(s); getnext(len); ;) { sum[k++]=nnext[i]; i=nnext[i]; } ; i>=; --i) printf("%d ",sum[i]); printf("%d\n",len); } ; }
第二次,自己A
#include <map> #include <set> #include <list> #include <cmath> #include <queue> #include <stack> #include <vector> #include <cstdio> #include <string> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int INF=0x3f3f3f3f; typedef long long ll; #define PU puts(""); #define PI(A) printf("%d\n",A) #define SI(N) scanf("%d",&(N)) #define SII(N,M) scanf("%d%d",&(N),&(M)) #define cle(a,val) memset(a,(val),sizeof(a)) #define rep(i,b) for(int i=0;i<(b);i++) #define Rep(i,a,b) for(int i=(a);i<=(b);i++) #define reRep(i,a,b) for(int i=(a);i>=(b);i--) ; /* ///////////////////////// C o d i n g S p a c e ///////////////////////// */ + ; int Next[MAXN]; int len; char x[MAXN]; int d[MAXN],cntd; void kmp_pre() { int i,j; j=Next[]=-; i=; while(i<len) { !=j&&x[i]!=x[j])j=Next[j]; Next[++i]=++j; } } int main() { #ifndef ONLINE_JUDGE freopen("C:\\Users\\Zmy\\Desktop\\in.txt","r",stdin); // freopen("C:\\Users\\Zmy\\Desktop\\out.txt","w",stdout); #endif while(~scanf("%s",x)) { cntd=; len=strlen(x); kmp_pre(); // for (int i=1;i<=len;i++) printf("%3d ",i);PU // for (int i=1;i<=len;i++) printf("%3d ",Next[i]);PU ;) { d[cntd++]=Next[i]; i=Next[i]; } ;i>=;i--) { printf("%d ",d[i]); } printf("%d\n",len); } ; }