【POJ2406】Power Strings(KMP算法)

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

Given two strings a and b we define a*b to be their concatenation. For example, if a = "abc" and b = "def" then a*b = "abcdef". If we think of concatenation as multiplication, exponentiation by a non-negative integer is defined in the normal way: a^0 = "" (the empty string) and a^(n+1) = a*(a^n).
题意:For each s you should print the largest n such that s = a^n for some string a.。即求一个字符串的最大重复子串的个数。
题解:用kmp中next[]函数来求解。
KMP不太了解的请看这篇这一篇
① len==1||s[next[len-1]]!=s[len-1] ans=1;
② len%(len-next[len])==0 ans= len/(len-next[len]);

#include <cstdio>
#include <cstring>
using namespace std;
char str[10000005];
int res;
int next[10000005];
void getNext(const char* pattern){
	next[0]=  -1;
	int k=-1,j=0;
	while(pattern[j] != '\0'){
		if(k!= -1 && pattern[k]!= pattern[j] )
		{k=next[k];}
		++j,++k;
		if(pattern[k]== pattern[j])
			next[j]=next[k];
		else  next[j]=k;
	}
}
int main(){
	freopen("1.txt","r",stdin);
	int len;
	while(scanf("%s",str)!=EOF){
		if(str[0]=='.') break;
		getNext(str);
		len=strlen(str);
		if(len==1 || str[next[len-1]]!=str[len-1]) res=1;
		if(len%(len-next[len])==0) res=len/(len-next[len]);
		printf("%d\n",res);
	}
}

我猜你可能也喜欢:

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 日