【hihoCoder 1419】重复旋律4

Description

小 Hi 平时的一大兴趣爱好就是演奏钢琴。我们知道一个音乐旋律被表示为长度为 N的数构成的数列。
小 Hi 在练习过很多曲子以后发现很多作品中的旋律有重复的部分。
我们把一段旋律称为( k , l )-重复的，如果它满足由一个长度为 l 的字符串重复了 k 次组成。如旋律 abaabaabaaba 是(4,3)重复的，因为它由 aba 重复 4 次组成。
小 Hi 想知道一部作品中 k 最大的(k,l)-重复旋律。

Input

一行一个仅包含小写字母的字符串。字符串长度不超过 100000。

Output

一行一个整数，表示答案 k。

Sample Input

babbabaabaabaabab

Sample Output

Hint

数据约束：
30%的数据 N<=1000
70%的数据 N<=10000
100%的数据 N<=100000

题解：

容易想到判断循环结延伸的长度就是i和i+k（k为循环结长度）的lcp,求两个后缀的lcp显然就是高度数组对应的一段的最小值

RMQ维护即可

接着就是难点,我们不必枚举每一个位置，只需枚举k的倍数

但是可能存在情况：使得i+l i+l+1 （1<=l<=k）使得次数大了1

但是显然我们可以O1的找出这个位置的答案即为 lcp(i-k+R%k,i+R%k) R为lcp(i,i+k) 可以画个图理解下

R%k是求出lcp不能形成新循环的多出来的一段那么我们就直接求lcp即可

 #include <algorithm>

 #include <iostream>

 #include <cstdlib>

 #include <cstring>

 #include <cstdio>

 #include <cmath>

 using namespace std;

 const int N=;

 int s[N],n=,rk[N],sa[N],tmp[N],k;char S[N];

 bool comp(int i,int j){

     if(rk[i]!=rk[j])return rk[i]<rk[j];

     int ri=i+k<=n?rk[i+k]:-;

     int rj=j+k<=n?rk[j+k]:-;

     return ri<rj;

 }

 void Getsa(){

     for(int i=;i<=n;i++){

         sa[i]=i;rk[i]=s[i];

     }

     for(k=;k<=n;k<<=){

         sort(sa+,sa+n+,comp);

         tmp[sa[]]=;

         for(int i=;i<=n;i++)tmp[sa[i]]=tmp[sa[i-]]+comp(sa[i-],sa[i]);

         for(int i=;i<=n;i++)rk[i]=tmp[i];

     }

 }

 int high[N];

 void Gethight(){

     int j,h=;

     for(int i=;i<=n;i++){

         j=sa[rk[i]-];

         if(h)h--;

         for(;i+h<=n && j+h<=n;h++)if(s[i+h]!=s[j+h])break;

         high[rk[i]-]=h;

     }

 }

 int f[N][];

 int query(int l,int r){

     int k=log(r-l+)/log();

     return min(f[l][k],f[r-(<<k)+][k]);

 }

 void prework(){

     int to;

     for(int i=;i<=n;i++)f[i][]=high[i];

     for(int j=;j<=;j++){

         for(int i=;i<=n-(<<j)+;i++){

             to=i+(<<(j-));

            if(f[i][j-]<f[to][j-])f[i][j]=f[i][j-];

             else f[i][j]=f[to][j-];

         }

     }

 }

 int lcp(int x,int y){

     if(rk[x]>rk[y])swap(x,y);

     return query(rk[x],rk[y]-);

 }

 int main()

 {

     //freopen("pp.in","r",stdin);

     scanf("%s",S);

     for(int i=,sz=strlen(S);i<sz;i++)

         s[++n]=S[i]-'a'+;

     Getsa();

     Gethight();

     prework();

     int ans=,to;

     for(int g=;g<=n;g++){

         for(int i=;i+g<=n;i+=g){

             to=lcp(i,i+g);

             ans=max(ans,to/g+);

             if(i-g+(to%g)>=){

                 ans=max(lcp(i-g+to%g,i+to%g)/g+,ans);

             }

         }

     }

     printf("%d\n",ans);

     return ;

 }

秒客网