题意
给出一个串，求重复次数最多的连续重复子串，输出字典序最小的。
分析
例8（P21）。
Sparse-Table算法预处理出任意两个后缀串的LCP。code
#include#include #include #include #include using namespace std;typedef unsigned long long ull;const int MAXN = 2e5 + 10;char s[MAXN];int sa[MAXN], t[MAXN], t2[MAXN], c[MAXN], n; // n 为 字符串长度 + 1，最后一位为数字 0int rnk[MAXN], height[MAXN];// 构造字符串 s 的后缀数组。每个字符值必须为 0 ~ m-1void build_sa(int m) { int i, *x = t, *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(int k = 1; k <= n; k <<= 1) { int p = 0; for(i = n - k; i < n; i++) y[p++] = i; for(i = 0; i < n; i++) if(sa[i] >= k) y[p++] = sa[i] - k; for(i = 0; i < m; i++) c[i] = 0; for(i = 0; i < n; i++) c[x[y[i]]]++; for(i = 0; 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] + k] == y[sa[i] + k] ? p - 1 : p++; if(p >= n) break; m = p; }}void getHeight() { int i, j, k = 0; for(i = 0; i < n; i++) rnk[sa[i]] = i; for(i = 0; i < n - 1; i++) { if(k) k--; j = sa[rnk[i] - 1]; while(s[i + k] == s[j + k]) k++; height[rnk[i]] = k; }}int dp[MAXN][30];void init() { for(int i = 0; i < n; i++) { dp[i][0] = height[i]; } for(int i = 1; (1 << i) < MAXN; i++) { for(int j = 0; j < n; j++) { dp[j][i] = min(dp[j][i - 1], dp[j + (1 << (i - 1))][i - 1]); } }}int query(int l, int r) { if(l > r) swap(l, r); l++; int k = (int)(log((double)r - l + 1) / log(2.0)); return min(dp[l][k], dp[r - (1 << k) + 1][k]);}int a[MAXN];int main() { int Case = 1; while(~scanf("%s", s) && s[0] != '#') { int L = strlen(s); n = L + 1; build_sa(128); getHeight(); init(); int mx = 0; int cnt = 0; // 寻找重复次数最多的连续子串单个子串的长度，可能有多种重复次数相同的子串 for(int l = 1; l <= L; l++) { for(int j = 0; j + l < L; j += l) { int k = query(rnk[j], rnk[j + l]); // lcp int res = k / l + 1; int pos = j - (l - (k % l)); if(pos >= 0 && k % l && query(rnk[pos], rnk[pos + l])) res++; if(res > mx) { mx = res; cnt = 0; a[cnt++] = l; } else if(res == mx) { a[cnt++] = l; } } } // 找字典序最小 int len = 0, st; for(int i = 1; i < n && !len; i++) { for(int j = 0; j < cnt; j++) { if(query(i, rnk[sa[i] + a[j]]) >= (mx - 1) * a[j]) { len = a[j]; st = sa[i]; break; } } } printf("Case %d: ", Case++); for(int i = st; i < st + len * mx; i++) { printf("%c", s[i]); } printf("\n"); } return 0;}