题目链接：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=36131
题意：给出一个长度为n的字符串，要求找到一些i，满足说从1~i为多个个的重复子串构成，并输出子串的个数。
题解：对kmp中预处理的数组的理解
//作者:1085422276 #include <cstdio> #include <cmath> #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; } //******************************* int n,p[1000001];char a[1000001]; int main() { int oo=1; while(scanf("%d",&n)!=EOF) { if(n==0)break; scanf("%s",a+1); memset(p,0,sizeof(p)); int j=0; for(int i=2;i<=n;i++) { while(j>0&&a[j+1]!=a[i])j=p[j]; if(a[j+1]==a[i])j++; p[i]=j; } cout<<"Test case #"<<oo++<<endl; for(int i=2;i<=n;i++) { if(p[i]>0&&i%(i-p[i])==0){ cout<<i<<" "<<i/(i-p[i])<<endl; } } cout<<endl; } return 0; }