zoj 1905𞓜poj2406 Power Strings（KMP 124; 124;暴力）

リンク:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=905
_。rz、最初は暴力+KMP硬生のタイムアウトです。
前処理配列の特性によって、やっと過ぎました。
2836474
2012-04-03 14:16:32
Acceepted
1905
C++
110
5064
zips123
たとえば
s:aば bab
P: 0 1 2 3 4
作り方はlen/(len-P[len]です。
前処理配列Pの由来を考えてみます。上の例では赤い部分が共通しています。すなわち6-4=2です。そして6/2=3です。

#include<stdio.h>
#include<string.h>
char s[1000005];	
int P[1000005];
int n;

void initP()
{
	P[0]=0;
	P[1]=0;
	int i,j=0,len=strlen(s);
	for(i=2;i<=len;i++)
	{
		while(j>0&&s[j]!=s[i-1])
			j=P[j];
		if(s[j]==s[i-1])
			j++;
		P[i]=j;
	}
}
int main()
{
	int len;
	while(~scanf("%s",s))
	{	
		if(s[0]=='.') break;
		initP();
		len=strlen(s);
		printf("%d
",len/(len-P[len]));
		
	}
	return 0;
}

cqlf
2406
Acceepted
5288 K
141 MS
G++
483 B
2012-04-03 14:34:24
poj上のデータと完全です。例えば、abbaa、上記のコードは間違いがあります。修正できるかどうかの判断を加えてください。

#include<stdio.h>
#include<string.h>
char s[1000005];	
int P[1000005];
int n;

void initP()
{
	P[0]=0;
	P[1]=0;
	int i,j=0,len=strlen(s);
	for(i=2;i<=len;i++)
	{
		while(j>0&&s[j]!=s[i-1])
			j=P[j];
		if(s[j]==s[i-1])
			j++;
		P[i]=j;
	}
}
int main()
{
	int len;
	while(~scanf("%s",s))
	{	
		if(s[0]=='.') break;
		initP();
		len=strlen(s);
		if(len%(len-P[len])!=0)
			printf("1
");
		else
			printf("%d
",len/(len-P[len]));
		
	}
	return 0;
}

discussで見た暴力の神様もいます。

#include<stdio.h>
#include<string.h>
char temp[1005000]={0};
int main()
{
	int i=0,N=0,ans=0,j=0;
	while(scanf("%s",&temp))
	{
		N=strlen(temp);
		if(N==1&&temp[0]=='.')
			break;
		for(i=1;i<=N;i++)
		{
			if(N%i==0)
			{
				for(j=i;j<N;j+=i)
				{
					if(strncmp(temp,temp+j,i))
					{
						break;
					}
				}
				if(j==N)
				{
					ans=N/i;
					break;
				}
			}
		}
		printf("%d
",ans);
	}
}