找重复次数最多的字串，如果有多解，要求字典序最小。
我也是跟着罗穗骞菊苣的论文才刷这道题的。
首先还是枚举一个循环节的长度L，如果它出现两次的话，一定会包含s[0], s[L], s[2L]这些相邻两个之间。
然后枚举相邻的两个，尽可能的向前和向后延伸，假设延伸长度为k，则重复次数为k / L + 1
向后延伸很自然的就是求一次LCP，这个用RMQ预处理一下就可以O(1)查询。
向前延伸就是考虑到，我们枚举的s[i*L]和s[(i+1)*L]并不一定是字串的开头，所以向前移动i - (k % i)个位置。
为什么向前移动这么多，就是因为这样的话，LCP的长度就正好是i的整数倍了。
所以向前移动以后，再求一次LCP，看看能否够i - (k % i)这么多，够的话这个串的重复次数再加1.
至于要字典序最小，就得用height数组天生自带字典序。把所有重复次数最多的长度记录下来，然后按字典序枚举，只要找到一组就输出。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; const int maxn = + ;
char s[maxn];
int n;
int sa[maxn], rank[maxn], height[maxn];
int t[maxn], t2[maxn], c[]; void build_sa(int n, int m)
{
int i, *x = t, *y = t2;
for(i = ; i < m; i++) c[i] = ;
for(i = ; i < n; i++) c[x[i] = s[i]]++;
for(i = ; i < m; i++) c[i] += c[i - ];
for(i = n - ; i >= ; i--) sa[--c[x[i]]] = i;
for(int k = ; k <= n; k <<= )
{
int p = ;
for(i = n - k; i < n; i++) y[p++] = i;
for(i = ; i < n; i++) if(sa[i] >= k) y[p++] = sa[i] - k;
for(i = ; i < m; i++) c[i] = ;
for(i = ; i < n; i++) c[x[y[i]]]++;
for(i = ; i < m; i++) c[i] += c[i - ];
for(i = n - ; i >= ; i--) sa[--c[x[y[i]]]] = y[i];
swap(x, y);
p = ; x[sa[]] = ;
for(i = ; i < n; i++)
x[sa[i]] = y[sa[i]]==y[sa[i-]] && y[sa[i]+k]==y[sa[i-]+k] ? p - : p++;
if(p >= n) break;
m = p;
}
} void build_height()
{
int k = ;
for(int i = ; i <= n; i++) rank[sa[i]] = i;
for(int i = ; i < n; i++)
{
if(k) k--;
int j = sa[rank[i] - ];
while(s[i + k] == s[j + k]) k++;
height[rank[i]] = k;
}
} int d[maxn][]; void init_RMQ()
{
for(int i = ; i < n; i++) d[i][] = height[i + ];
for(int j = ; ( << j) <= n; j++)
for(int i = ; i + ( << j) - < n; i++)
d[i][j] = min(d[i][j-], d[i + (<<(j-))][j-]);
} int RMQ(int L, int R)
{
int k = ;
while( ( << (k+)) <= (R - L + ) ) k++;
return min(d[L][k], d[R-(<<k)+][k]);
} int LCP(int i, int j)
{
i = rank[i] - ; j = rank[j] - ;
if(i > j) swap(i, j);
return RMQ(i + , j);
} int a[maxn], cnt, maxl; int main()
{
//freopen("in.txt", "r", stdin); int kase = ;
while(scanf("%s", s) == && s[] != '#')
{
n = strlen(s);
build_sa(n + , );
build_height();
init_RMQ(); cnt = maxl = ;
for(int i = ; i < n; i++)
{
for(int j = ; j + i < n; j += i)
{
int k = LCP(j, j + i);
int t = k / i + ;
int left = i - (k % i);
int head = j - left;
if(head >= && LCP(head, head + i) >= left) t++;
if(t > maxl)
{
cnt = ;
a[cnt++] = i;
maxl = t;
}
if(t == maxl) a[cnt++] = i;
}
} int len = -, st;
for(int i = ; i <= n && len == -; i++)
{
for(int j = ; j < cnt; j++)
{
int l = a[j];
if(LCP(sa[i], sa[i] + l) >= (maxl - ) * l)
{
len = l;
st = sa[i];
break;
}
}
} printf("Case %d: ", ++kase);
for(int i = ; i < len * maxl; i++) printf("%c", s[st + i]);
puts("");
} return ;
}
代码君