hdu 1358 Period (kmp，求字符串的周期)
题意：给一个字符串，求这个字符串的每个前缀（包括本身）的能否由k个子串组成（K>1）
思路：和poj 2406 比较类似。。
结论：字符编号从0开始，如果又i%(i-next[i])==0，则i前面的 串为一个轮回串，其中轮回子串出现i/(i-next[i])次。
证明类似之前最小覆盖中的，不断的等价交换，两两相等...（这个证明在字符串这里总是遇到2333）
然而其实我。。。做的时候。。并没有想到去证明。。。而是打印出了nxt数组然后找规律求得2333.
之前一直觉得找规律不是什么拿的上台面的做法。。。但是今年打了几场多校。。尤其是电子科大的那场。。。我发现。。。其实有的题目的正解就是找规律，猜结论。。。
&nbs;
/* ***********************************************
Author :111qqz
Created Time :2016年08月11日 星期四 03时20分44秒
File Name :code/hdu/1358.cpp
************************************************ */
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <deque>
#include <ctime>
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair
using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const int N=1E6+7;
int nxt[N];
char a[N];
int n ;
void getnxt( char *s)
{
int i = 0 ;
int j = -1;
nxt[0] = -1;
int n = strlen(s);
while (i<n)
if (j==-1||s[i]==a[j]) nxt[++i]=++j;
else j = nxt[j];
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("code/in.txt","r",stdin);
#endif
int cas = 0 ;
while (~scanf("%d",&n))
{
if (n==0) break;
printf("Test case #%d\n",++cas);
scanf("%s",a);
getnxt(a);
// for ( int i = 0 ; i <= n ; i++ ) printf("nxt[%d]:%d\n",i,nxt[i]);
for ( int i = 1 ; i <= n ; i++)
{
if (nxt[i]==0) continue; //因为题目要求k>1
int tmp = i-nxt[i];
if (i%tmp==0)
printf("%d %d\n",i,i/tmp);
}
printf("\n");
}
#ifndef ONLINE_JUDGE
fclose(stdin);
#endif
return 0;
}