题目描述

哈希一下，从小到大找不同块，找到一个符合的块直接输出答案即可

算法1

虽然感觉是枚举但是，感觉时间复杂度没呢么高，应该是$O(nlogn)$级别的

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e2+5;
typedef unsigned long long ll;
const ll base=13331;
ll h[maxn],p[maxn];
char s[maxn];
ll get(ll l,ll r)
{
    return h[r]-h[l-1]*p[r-l+1];
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    while(cin>>s+1&&s[1]!='.')
    {
        p[0]=1;
        ll len=strlen(s+1);
        for(int i=1; i<=len; i++)
        {
            h[i]=h[i-1]*base+s[i]-'a';
            p[i]=p[i-1]*base;
        }
        ll maxx=1;
        int k=1;
        while(1)
        {
            bool fla=true;
            ll j,ans=1;
            if(len%k==0)
            {
                j=len/k;
                if(j==1)
                    break;
                for(int i=1; i+2*k-1<=len; i+=k)
                {
                    if(get(i,i+k-1)==get(i+k,i+2*k-1))
                        ans++;
                    else
                    {
                        fla=false;
                        break;
                    }
                }
                if(fla)
                {
                    maxx=max(maxx,ans);
                    break;
                }
            }
            k++;
        }
        cout<<maxx<<endl;
    }
}