pku2406.cpp

来自「这是ACM 方面的资料 是PKU的 北京大学的出来的」· C++ 代码 · 共 47 行

#include <stdio.h>
#define SIZE 1000010

char s[SIZE];
int next[SIZE];

void kmp()
{
	int i, p = 0, l;
	next[0] = -1;
	i = 1;
	while (s[i] != '\0')
	{
		if ( p < 0 || s[i] == s[p])
		{
			p++; i++;
			next[i] = p;
		}
		else
		{
			p = next[p];
		}
	}
	l = i;
	if (l % (l - next[l]) == 0)
	{
		printf("%d\n", l / (l - next[l]));
	}
	else
	{
		printf("1\n");
	}
}
int main()
{
	while (scanf("%s", s) != -1)
	{
		if (s[0] == '.')
		{
			break;
		}
		kmp();
	}
	return 0;
}