poj 2406 Power Strings

Recommended for you: Get network issues from WhatsUp Gold. Not end users.

Not for next KMP optimized directly by the

Power Strings
Time Limit: 3000MS Memory Limit: 65536K
Total Submissions: 28897 Accepted: 12062

Description

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).

Input

Each test case is a line of input representing s, a string of printable characters. The length of s will be at least 1 and will not exceed 1 million characters. A line containing a period follows the last test case.

Output

For each s you should print the largest n such that s = a^n for some string a.

Sample Input

abcd
aaaa
ababab
.

Sample Output

1
4
3

Hint

This problem has huge input, use scanf instead of cin to avoid time limit exceed.

Source

Waterloo local 2002.07.01

[Submit]   [Go Back]   [Status]   [Discuss]

/*=============================================================================
#     FileName: 2406.cpp
#         Desc: poj 2406
#       Author: zhuting
#        Email: 
#     HomePage: my.oschina.net/locusxt
#      Version: 0.0.1
#    CreatTime: 2013-12-21 14:45:54
#   LastChange: 2013-12-21 14:45:54
#      History:
=============================================================================*/
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <algorithm>

#define maxn 1000010

char str[maxn];

/*The direct use of next methods, optimization can not solve this problem*/
int* get_next(char* a)
{
	int len = strlen(a);
	if (len <= 0) return NULL;
	int j = 0, k = -1;
	int* n = new int[len + 1];/*n[len+1]The length of the longest length of record starts with a[0] and a[len-1] at the end of the same string*/
	n[0] = -1;
	while(j <len)
	{
		if (k >= 0 && a[k] != a[j])
		{
			k = n[k];
		}
		++j;
		++k;
		n[j] = k;
	}
	return n;
}

int main()
{
	while(scanf("%s", str) != EOF)
	{
		if (str[0] == '.') break;
		int len = strlen(str);
		int* tmp = get_next(str);

		int delta = len - tmp[len];
		if (len % delta || str[len - 1] != str[tmp[len] - 1])/*Pay special attention to the situation of aaab*/
			printf("1\n");
		else
			printf("%d\n", len / delta);
		
		/*test*/
		/*
		for (int i = 0; i <= len; ++i)
		{
			printf("%d ", tmp[i]);
		}
		printf("\n");*/
	}

	return 0;
}



Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download

Posted by Opie at February 01, 2014 - 11:16 AM