题目描述

逆向思维，思考n应满足什么条件？如何找到重复单元？

样例

#include<iostream>
using namespace std;
int main()
{
    string s;
    while(cin>>s,s!=".")//每一次输入
    {
        int len=s.size();
        int n;//这个就是要求的你，倒着推n应该满足什么条件
        for(n=len;n>0;n--)//n从最大开始，例如aaaaa，n就和总长度相等
        if(len%n==0)//如果可以，n一定能够被总长度整除，所以n从最长开始--，直到可以被len整除；能被整除只是第一关，还得往后看，是否满足下面的条件
        {
            int m=len/n;//n把总字符串分成n段，每段有几个？——m=len/n；找到了重复单元的长度，为了后面你能知道输出几个
            string r;//存放你最后用重复单元拼出来的
            string str=s.substr(0,m);//这个是重复单元
            for(int i=0;i<n;i++)//把重复单元拼n次
            r+=str;
            if(r==s)//如果拼出来的r和原来的s相等，说明n就是对的
           { cout<<n<<endl;break;}//输出就行了
        }

    }
    return 0;

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla