首页 > 代码库 > POJ2406Power Strings

POJ2406Power Strings

2024-07-03 11:24:30   225人阅读

来源:http://poj.org/problem?id=2406 

Power Strings
Time Limit: 3000MS Memory Limit: 65536K
Total Submissions: 30293 Accepted: 12631

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

题意:不多解释

这题书上说是用KMP来做，自己开始也尝试这样做，但后来发现根本就没有这个必要~~~几个简单的字符串处理函数就可以A掉了
代码:

#include<iostream>
#include<string>
using namespace std;
int main()
{
	string s;
	while(cin>>s&&s!=".")
	{
		int L=s.size();
		for(int i=1;i<=L;i++)
		{
			int temp;
			string  str="";
			if(L%i==0)
			{
			temp=L/i;
			t=s.substr(0,i);
			for(int j=0;j<temp;j++)
			str+=t;
			if(str==s)
			{
				cout<<temp<<endl;
				break;
			} 
			}
		}
	}
return 0;
}


联系
我们