【POJ1961】Period(KMP算法,next函数)

Categories: 数据结构和算法
Comments: No Comments
Published on: 2011 年 05 月 19 日

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.
题意:即求一个字符串的最大重复字串。
题解:基本跟POJ2406一样,改改输出格式,系买一送一类

#include <cstring>
#include<cstdio>
using namespace std;
#define maxlen 1000002
int P[maxlen];
char str[maxlen];
int main(){
	freopen("1.txt","r",stdin);
	int n = 1,len;//测试数据组数计数器
	while(scanf("%d",&len)!=EOF && len!=0){
		scanf("%s",str);
		P[1] = 0;//P[]下标从1开始
		int j = 0;
		for (int i=2;i<=len;i++){
			//除非j==0,否则失配就要右滑
			while( j>0 && str[j]!=str[i-1] )
				j = P[j];
			//配成的话,j要移动,事实上不移动的话P[i]=j+1
			if ( str[j] == str[i-1] )
				j++;
			//为了使得代码简洁,将两种情况(j==0和匹配)的赋值合并,但是有些损失可读性
			P[i] = j;
		}
		//k-P[k]是字符串向右移动的位数,总长度除以之,如能除尽,
		//结果就是重复次数,否则重复次数为1
		printf("Test case #%d\n",n++);
		for (int k=2;k<=len;k++)
			if ( k%(k-P[k])==0 && k/(k-P[k])!=1)
					printf("%d %d\n",k,k/(k-P[k]));
		printf("\n");
	}
}

我猜你可能也喜欢:

No Comments - Leave a comment

Leave a comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>


Welcome , today is 星期二, 2017 年 10 月 24 日