ccabababc
daabbccaa
#

Case 1: ababab
Case 2: aa

题意：求给出一个串，求重复次数最多的连续重复子串。
思路：膜拜后缀数组神论文和cxlove的题解：比较容易理解的部分就是枚举长度为L，然后看长度为L的字符串最多连续出现几次。
既然长度为L的串重复出现，那么str[0],str[l],str[2l]……中肯定有两个连续的出现在字符串中。
那么就枚举连续的两个，然后从这两个字符前后匹配，看最多能匹配多远。
即以str[il],str[il+l]前后匹配，这里是通过查询suffix(il),suffix(il+l)的最长公共前缀，通过rank值能找到il,与il+l的排名，我们要查询的是这段区间的height的最小值，通过RMQ预处理，达到查询为0(1)的复杂度，
设LCP长度为M, 则答案显然为M / L + 1, 但这不一定是最好的, 因为答案的首尾不一定再我们枚举的位置上. 我的解决方法是, 我们考虑M % L的值的意义, 我们可以认为是后面多了M % L个字符, 但是我们更可以想成前面少了(L - M % L)个字符! 所以我们求后缀jL - (L - M % L)与后缀(j + 1) * L - (L - M % L)的最长公共前缀。即把之前的区间前缀L-M%L即可。然后把可能取到最大值的长度L保存，由于 题目要求字典序最小，通过sa数组进行枚举，取到的第一组，肯定是字典序最小的。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
const int maxn = 100010;

int sa[maxn]; 
int t1[maxn], t2[maxn], c[maxn];
int rank[maxn], height[maxn];

void build_sa(int s[], int n, int m) {
    int i, j, p, *x = t1, *y = t2;
    for (i = 0; i < m; i++) c[i] = 0;
    for (i = 0; i < n; i++) c[x[i] = s[i]]++;
    for (i = 1; i < m; i++) c[i] += c[i-1];
    for (i = n-1; i >= 0; i--) sa[--c[x[i]]] = i;

    for (j = 1; j <= n; j <<= 1) {
        p = 0;
        for (i = n-j; i < n; i++) y[p++] = i;
        for (i = 0; i < n; i++) 
            if (sa[i] >= j) 
                y[p++] = sa[i] - j;
        for (i = 0; i < m; i++) c[i] = 0;
        for (i = 0; i < n; i++) c[x[y[i]]]++;
        for (i = 1; i < m; i++) c[i] += c[i-1];
        for (i = n-1; i >= 0; i--) sa[--c[x[y[i]]]] = y[i];

        swap(x, y);
        p = 1, x[sa[0]] = 0;
        for (i = 1; i < n; i++) 
            x[sa[i]] = y[sa[i-1]] == y[sa[i]] && y[sa[i-1]+j] == y[sa[i]+j] ? p-1 : p++;

        if (p >= n) break;
        m = p;
    }
}

void getHeight(int s[],int n) {
    int i, j, k = 0;
    for (i = 0; i <= n; i++)
        rank[sa[i]] = i;

    for (i = 0; i < n; i++) {
        if (k) k--;
        j = sa[rank[i]-1];
        while (s[i+k] == s[j+k]) k++;
        height[rank[i]] = k;
    }
}
int dp[maxn][30];
char str[maxn];
int r[maxn];
int a[maxn];

void initRMQ(int n) {
    int m = floor(log(n+0.0) / log(2.0));  
    for (int i = 1; i <= n; i++) 
        dp[i][0] = height[i];  

    for (int i = 1; i <= m; i++) {  
        for (int j = n; j; j--) {  
            dp[j][i] = dp[j][i-1];  
            if (j+(1<<(i-1)) <= n)  
                dp[j][i] = min(dp[j][i], dp[j+(1<<(i-1))][i-1]);  
        }  
    }  
}

int lcp(int l, int r) {
    int a = rank[l], b = rank[r];  
    if (a > b) 
        swap(a,b);  
    a++;  
    int m = floor(log(b-a+1.0) / log(2.0));  
    return min(dp[a][m], dp[b-(1<<m)+1][m]);  
}

int main() {
    int cas = 1;
    while (scanf("%s", str) != EOF && str[0] != ‘#‘) {
        int n = strlen(str);
        for (int i = 0; i <= n; i++)
            r[i] = str[i];

        build_sa(r, n+1, 128);
        getHeight(r, n);
        initRMQ(n);

        int cnt = 0, Max = 0;
        for (int l = 1; l < n; l++) {
            for (int i = 0; i + l < n; i += l) {
                int tmp = lcp(i, i+l);
                int step = tmp / l + 1;
                int k = i - (l - tmp % l);
                if (k >= 0 && tmp % l) 
                    if (lcp(k, k+l) >= tmp)
                        step++;

                if (step > Max) {
                    Max = step;
                    cnt = 0;
                    a[cnt++] = l;
                }
                else if (step == Max)
                    a[cnt++] = l;
            }    
        }

        int len = -1, st;
        for (int i = 1; i <= n && len == -1; i++) 
            for (int j = 0; j < cnt; j++) {
                int l = a[j];
                if (lcp(sa[i], sa[i]+l) >= (Max - 1) * l) {
                    len = l;
                    st = sa[i];
                    break;
                }
            }

        str[st + len * Max] = 0;
        printf("Case %d: %s\n", cas++, str + st);
    }
    return 0;
}

POJ - 3693 Maximum repetition substring(后缀数组求重复次数最多的连续重复子串)