鄙人才疏学浅，此中鄙陋甚多，望海涵！

题目描述

给定两个字符串a和b,我们定义a*b为他们的连接。

例如，如果a=”abc” 而b=”def”， 则a*b=”abcdef”。

如果我们将连接考虑成乘法，一个非负整数的乘方将用一种通常的方式定义：a0=””(空字符串)，a(n+1)=a∗(an)。

输入格式
输入包含多组测试样例，每组测试样例占一行。

每组样例包含一个字符串s，s的长度不超过100。

最后的测试样例后面将是一个点号作为一行。

输出格式
对于每一个s，你需要输出最大的n，使得存在一个字符串a，让s=an。

样例

输入样例：
abcd
aaaa
ababab
.
输出样例：
1
4
3

算法1

STL

C++ 代码

#include<iostream>

using namespace std;

int main()
{
    string s;
    while(cin>>s,s!=".")
    {
        for(int i=s.size();i;i--)
        {
            if(s.size()%i==0)
            {
                string str,a;
                int m=s.size()/i;
                str+=s.substr(0,m);
                for(int j=0;j<i;j++)
                a+=str;
                if(a==s)
                {
                    cout<< i <<endl;
                    break;
                }
            }
        }
    }
    return 0;
}

算法2

KMP求最小循环节

C++ 代码

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N=110;

int ne[N];
int n;

int main()
{
    char s[N];
    while(cin>>s+1 && s[1]!='.')
    {
        int n=strlen(s+1);
        for(int i=2,j=0;i<=n;i++)
        {
            while(j && s[i]!=s[j+1]) j=ne[j];
            if(s[i]==s[j+1]) j++;
            ne[i]=j;
        }
        cout<< n/(n-ne[n]) <<endl;
    }
    return 0;
}