10298

#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>

using namespace std;

int lps[1000005];

void prefixArray(string s)
{
	memset(lps,0,sizeof(lps));
	int len=0;//length of prev longest prefix
	int i=1;
	lps[0]=0;
	int length = s.size();
	while(i<length)
	{
		if(s[i]==s[len])
		{
			len+=1;
			lps[i]=len;
			i+=1;
		}
		else
		{
			if(len!=0)
			{
				len = lps[len-1];
			}
			else
			{
				lps[i]=0;
				i+=1;
			}
		}
	}
}
int main()
{
	string s;
	int lastval,minimal_length_of_repeated_string;
	while(cin>>s)
	{
		if(s==".")
		break;
		prefixArray(s);
		lastval = lps[s.size()-1];
		minimal_length_of_repeated_string = s.size()-lastval;
		if(s.size()%minimal_length_of_repeated_string==0)
		printf("%d\n",s.size()/minimal_length_of_repeated_string);
		else
		printf("1\n");
	}
	return 0;
}

 

Leave a Reply

Your email address will not be published. Required fields are marked *