Period

3
aaa
12
aabaabaabaab
0

Test case #1
2 2
3 3

Test case #2
2 2
6 2
9 3
12 4

一直在思索这个题目，发现自己对next数组理解还是不深刻。

举个简单的例子：

//============================================================================
// Name        : KMP_hdu1358.cpp
// Author      : vit
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <string.h>
#include <stdio.h>

using namespace std;

int i, j, m ,n;
char str[1000001];
int next[1000001];
int ch;
int no;

void GetNext() {
	j = 0;
	i = -1;
	next[0] = -1;
	while (j < n) {
		if (i == -1 || str[i] == str[j]) {
			i++, j++;
			next[j] = i;
		} else {
			i = next[i];
		}
	}
}

int main() {
	no = 1;
	while(cin >> n){
		if(n == 0)
			break;
		scanf("%s", str);
		GetNext();
		printf("Test case #%d\n", no);
		no++;
		for(i = 2; i <= n; i++){
			ch = i - next[i];
			if(i % ch == 0){//可以想成（i - 1） - 0 + 1
				if(i / ch > 1){//重复次数大于1
					printf("%d %d\n",i,i / ch);
				}
			}
		}
		printf("\n");
	}
	return 0;
}

//优化的算法

void GetNextval(){//用此算法生成的nextval数组，不能用上面的算法进行计算。原因很简单：把相同的串重复跳转判断的部分放在了nextval生成里面，所以减少KMP的比较次数的同时，也造成了无法找到重复串的次数。
	j = 0;
	i = -1;
	nextval[0] = -1;
	while(j < n){
		if(i == -1 || str[i] == str[j]){
			i++, j++;
			if(str[i] == str[j])
				nextval[j] = i;
			else
				nextval[j] = nextval[i];
		} else
			i = nextval[i];
	}
}

hdu1358 Period,布布扣,bubuko.com

hdu1358 Period

原文：http://blog.csdn.net/svitter/article/details/22959285