问题 D: 4.5.17 Power Strings
时间限制: 3 Sec 内存限制: 64 MB
题目描述
Given two strings a and b we define ab to be their concatenation. For example, if a = "abc" and b = "def" then ab = "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).
输入
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.
输出
For each s you should print the largest n such that s = a^n for some string a.
样例输入
abcd
aaaa
ababab
.
样例输出
1
4
3
#include <iostream>
#include <string>
using namespace std;
int judge(string &s)
{
char a=s[0];
int locate=s.find(a,1);
int length = s.length();
while(locate>0) //找不到第一个元素时会返回-1，找不到重复时也会返回-1
{
int times = s.length() / locate; //重复次数
int i = locate;
if (length % locate == 0) //如果重复，长度必为第一次出现字母的前面这个小字符串长度的整数倍
{
/*比较locate之前的字符串是否从locate开始重复*/
string b(s, 0, locate);
for (;i!=length;i+=locate)
{
string c(s, i, locate); //从i开始查找字符串s中前locate个字符在当前串中的位置
if (b != c)
break;
}
}
if (i == length)
return times;
locate=s.find(a,locate+1); //从上一次找到的位置开始寻找
}
return 1;
}
int main()
{
string s;
string a = ".";
while(cin>>s&&s!= a )
{
cout<<judge(s)<<endl;
}
return 0;
}
