Power Strings

问题 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;
}