首页 > ACM题库 > HDU-杭电 > HDU 1358 Period-KMP-[解题报告] C++
2013
12-09

HDU 1358 Period-KMP-[解题报告] C++

Period

问题描述 :

For each prefix of a given string S with N characters (each character has an ASCII code between 97 and 126, inclusive), we want to know whether the prefix is a periodic string. That is, for each i (2 <= i <= N) we want to know the largest K > 1 (if there is one) such that the prefix of S with length i can be written as AK , that is A concatenated K times, for some string A. Of course, we also want to know the period K.

输入:

The input file consists of several test cases. Each test case consists of two lines. The first one contains N (2 <= N <= 1 000 000) � the size of the string S. The second line contains the string S. The input file ends with a line, having the number zero on it.

输出:

For each test case, output “Test case #” and the consecutive test case number on a single line; then, for each prefix with length i that has a period K > 1, output the prefix size i and the period K separated by a single space; the prefix sizes must be in increasing order. Print a blank line after each test case.

样例输入:

3
aaa
12
aabaabaabaab
0

样例输出:

Test case #1
2 2
3 3

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

http://acm.hdu.edu.cn/showproblem.php?pid=1358

题目大意:给出一个长度为 n 的字符串,求该字符串的循环前缀的长度,和循环次数;

示例:abababab

前4个字符,循环字串为ab,有2个循环周期 ab|ab

前6个字符,循环字串为ab,有3个循环周期 ab|ab|ab

前8个字符,循环字串为ab,有4个循环周期 ab|ab|ab|ab

输出:

4 2

6 3

8 4

#include<stdio.h>
#define SIZE 1000006
int next[SIZE];
char str[SIZE];

void getnext(int n)
{
	int i=0,j=-1;
	next[0]=-1;
	while(i<n){
		if(j==-1 || str[i]==str[j]){
			i++;
			j++;
			next[i] = j;
		}
		else{
			j = next[j];
		}
	}
}
int main()
{
	int nT=1,n,i,mixed,circulate;
	while(scanf("%d",&n),n){
		getchar();
		gets(str);
		getnext(n);
		printf("Test case #%d\n",nT++);
		for(i=1;i<=n;i++){
			mixed = 2*next[i]-i;       //重叠部分
			circulate = next[i]-mixed; //循环节长度
			if(mixed>=0 && i%circulate==0){
				printf("%d %d\n",i,i/circulate);
			}
		}
		printf("\n");
	}
	return 0;
}

解题报告转自:http://blog.csdn.net/crazy_xiaohe/article/details/8910864


  1. 你的理解应该是:即使主持人拿走一个箱子对结果没有影响。这样想,主持人拿走的箱子只是没有影响到你初始选择的那个箱子中有奖品的概率,但是改变了其余两个箱子的概率分布。由 1/3,1/3 变成了 0, 2/3