Str

两个串 s 和 t 相似当且仅当它们所有的字符的数量都相同。
比较s的两个子串是否相似是 O(26) 的。
暴力枚举 n 的因子 k 。比较 n/k 个串是否相似。

#include<bits/stdc++.h>
using namespace std;
string hh;
int len;
int c[30][100001];
inline int lb (int n)
{
    return n&-n;
}
inline void add(int w1,int w2,int v)
{
    while(w1<=len)
    {
        c[w2][w1]+=v;
        w1+=lb(w1);
    }
    return;
}
inline int sum(int w1,int w2)
{
    int ans=0;
    while(w1>=1)
    {
        ans+=c[w2][w1];
        w1-=lb(w1);
    }
    return ans;
}
int help[30];
inline int ok(int len2)
{
    for(int i=1;i<=26;i++)
  help[i]=sum(len2,i);
    for(int i=len2*2;i<=len;i+=len2)
    {
        for(int j=1;j<=26;j++)
        {
            long long a=(long long )help[j]*i/len2;
            long long b=(long long )sum(i,j);
            if(a!=b)
    return 0;
        }
    }
    return 1;
}
int main() 
{
 ios::sync_with_stdio(0);
 cin>>hh;
 len=hh.length();
 for(int i=1;i<=len;i++)
 {
  add(i,hh[i-1]-'a'+1,1);
 }
 for(int i=1; i*2<=len; i++) 
 {
  if(len%i==0)
  {
   if(ok(i))
   {
    cout<<hh.substr(0,i)<<endl;
    return 0;
   }
  }
 }
 cout<<-1<<endl;
}