跳转至

后缀数组（SA）

对于一个长为 \(n\) 的字符串 \(s\)，它有 \(n\) 个后缀。我们将这 \(n\) 个后缀按照字典序从小到达排序，即可得到后缀数组 \(sa[i]\)，它表示字典序第 \(i\) 小的后缀是 \([sa[i],n]\)。相应的，我们有排名数组 \(rk[i]\)，它是后缀数组的逆，表示 \([i,n]\) 后缀是所有后缀中排名第 \(rk[i]\) 小的。

后缀数组可以高效解决许多字符串问题。

倍增法求后缀数组

对于 \(2\) 的整数次幂 \(w=2^k\)，我们暂时只考虑每个后缀长度为 \(w\) 的前缀 \([i,\min(i+w-1,n)]\)，并按这些部分对后缀进行排序。如果两个后缀的 \(w\) 前缀相等，则它们的 \(rk\) 也相等。当 \(w\ge n\) 时，所有后缀的排列顺序就是后缀数组。

SA1

我们现在考虑如何从 \(w=w_0\) 的 \(sa\) 和 \(rk\) 快速递推到 \(w=2w_0\) 的 \(sa\) 和 \(rk\)。这个递推的过程可以视为一个双关键字排序的过程：\(rk[i]\) 为第一关键字，\(rk[i+w]\) 为第二关键字。

SA2

注意到 \(rk[i]\) 的值不超过 \(n\)，因此我们可以使用一些基于值域的排序算法，将时间复杂度做到 \(O(n)\)，比如基数排序。事实上，通过一些预处理，我们可以直接使用魔改的计数排序，码量较小。

考虑计数排序。先将所有元素按照第一关键字 \(rk[i]\) 放入桶数组中。接着，我们只需要按照第二关键字将所有元素依次取出，即可得到排序结果。

具体的，我们设 \(tp[i]\) 表示第二关键字排名为 \(i\) 的那个后缀。简单的讲，\(tp[i]\) 就是 \(sa[i]-w\)。考虑特殊情况：对于 \(sa[i]\le w\)，不可能作为其它后缀的第二关键字，因此将它们从 \(tp\) 序列中删除。对于 \(tp[i]\in [n-w+1,n]\) 的后缀，它们的第二关键字为空，字典序最小，应该排在 \(tp\) 的最前面。

p = 0;
for(int i = n - w + 1; i <= n; i++) {
    tp[++p] = i; // 第二关键字为空的那些前缀，排在 tp 的最前面
}
for(int i = 1; i <= n; i++) {
    if(sa[i] > w) tp[++p] = sa[i] - w; 
    // 如果当前后缀是某个后缀对应的第二关键字，就将那个后缀加入 tp
}

那么，在计数排序中，我们只需要按 \(n\rightarrow 1\) 的顺序遍历 \(tp\)，将对应的元素从桶中取出即可：

void sort() {
    // m 表示 rk 的值域
    for(int i = 1; i <= m; i++) cnt[i] = 0; // 计数排序模板
    for(int i = 1; i <= n; i++) ++cnt[rk[i]]; // 计数排序模板
    for(int i = 1; i <= m; i++) cnt[i] += cnt[i - 1]; // 计数排序模板
    for(int i = n; i >= 1; i--) sa[cnt[rk[tp[i]]]--] = tp[i]; // tp 倒序取出元素
}

但是计数排序只得到了 \(sa\)，下一轮使用的 \(rk\) 数组还需要我们求得。同时，相等的元素还要去重：

for(int i = 1; i <= n; i++) tp[i] = rk[i]; // 一数组两用，存储原来的 rk
rk[sa[1]] = 1; // 初值
for(int i = 2; i <= n; i++) {
    if(tp[sa[i]] == tp[sa[i - 1]] && tp[sa[i] + w] == tp[sa[i - 1] + w]) {
    // 条件的后半部分可能发生越界。
    // 然而，凡是 sa[i] > n - w + 1 的情况，前半部分条件都不可能成立；
    // 由于短路，在这种情况下程序不会判断后半部分条件。
    // 经过测试，如果交换两者的顺序，极端情况确实会发生 RE。
        rk[sa[i]] = rk[sa[i - 1]];
    } else rk[sa[i]] = rk[sa[i - 1]] + 1;
}
m = rk[sa[n]]; // 记录新的值域
if(m == n) break; // 常数优化

到这里，SA 的主体部分已经完成。但我们需要处理起始情况：只按照后缀的第一个字符排序，生成 \(sa\) 数组：

for(int i = 1; i <= n; i++) rk[i] = s[i];
for(int i = 1; i <= n; i++) tp[i] = i; // sort 函数要求 tp 必须为一个排列
sort();

倍增最多 \(\log n\) 轮，因此总时间复杂度为 \(O(n\log n)\)。

完整代码 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
int sa[N], rk[N], tp[N], cnt[N];

void sort() {
    for(int i = 1; i <= m; i++) cnt[i] = 0;
    for(int i = 1; i <= n; i++) ++cnt[rk[i]];
    for(int i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
    for(int i = n; i >= 1; i--) sa[cnt[rk[tp[i]]]--] = tp[i];
}

void get_SA() {
    m = 128;
    for(int i = 1; i <= n; i++) rk[i] = s[i];
    for(int i = 1; i <= n; i++) tp[i] = i;
    sort();
    for(int w = 1, p; w < n; w <<= 1) {
        p = 0;
        for(int i = n - w + 1; i <= n; i++) tp[++p] = i;
        for(int i = 1; i <= n; i++) {
            if(sa[i] > w) tp[++p] = sa[i] - w;
        }
        sort();
        for(int i = 1; i <= n; i++) tp[i] = rk[i];
        rk[sa[1]] = 1;
        for(int i = 2; i <= n; i++) {
            if(tp[sa[i]] == tp[sa[i - 1]] && tp[sa[i] + w] == tp[sa[i - 1] + w]) {
                rk[sa[i]] = rk[sa[i - 1]];
            } else rk[sa[i]] = rk[sa[i - 1]] + 1;
        }
        if(rk[sa[n]] == n) break;
        m = rk[sa[n]];
    }
}

height 数组

我们有时用正整数 \(i\) 指代 \([i,n]\) 后缀。

定义 \(ht[i]=lcp\big(sa[i - 1], sa[i]\big)\)，其中 \(i\in [2,n]\)。

引理 \(1\)

对于任意三个后缀 \(i,j,k\) 满足 \(rk[i]<rk[j]<rk[k]\) 有

\[ lcp(i,k)=\min\big(lcp(i,j),lcp(j,k)\big) \]
证明

记 \(x=\min\big(lcp(i,j),lcp(j,k)\big)\)。

显然，\(lcp(i,k)\ge x\)，考虑证明 \(lcp(i,k)\le x\)。

假设 \(lcp(i,k)>x\)。考虑第 \(x+1\) 位，有

\[ suf(k)_{x+1}=suf(i)_{x+1}\ne suf(j)_{x+1} \]

因为 \(rk[i]\le rk[j]\)，\(i\) 和 \(j\) 的前 \(x\) 位相同，有

\[ suf(k)_{x+1}=suf(i)_{x+1}< suf(j)_{x+1} \]

然而 \(rk[k]>rk[j]\)，\(j\) 和 \(k\) 的前 \(x\) 位也相同，和字典序从小到大矛盾。证毕。

推论

对于任意两个后缀 \(i,j\) 满足 \(rk[i]<rk[j]\)，有

\[ lcp(i,j)=\min_{rk[i]<k\le rk[j]}\{ht[k]\} \]

归纳法易证。

根据推论，如果我们得到了 \(ht\) 数组，即可使用 \(st\) 表快速查询两个后缀的 \(lcp\)。

我们还有一些重要的引理需要介绍。依据它们，我们才能在线性时间内求出所有 \(ht\)。

引理 \(2\)

对于 \(i,j\) 满足 \(j<i\)，有

\[ lcp(sa[i],sa[j])\le lcp(sa[i], sa[i-1]) \]

这个引理告诉我们：在 \(sa\) 中相邻的字符串，\(lcp\) 达到极大值。

证明

由推论易证。区间越短，最小值越大，\(lcp\) 越长。

引理 \(3\)

对于后缀 \(i\in [2,n]\) 且满足 \(rk[i]>1\)，有

\[ ht\big[rk[i]\big]\ge ht\big[rk[i-1]\big]-1 \]
证明

考虑构造。记 \(j=sa\big[rk[i-1]-1\big]\)，因此 \(ht\big[rk[i-1]\big]=lcp(i-1,j)\)。

因为 \(rk[j]<rk[i-1]\)，所以 \(rk[j+1]<rk[i]\)。根据引理 \(2\)，有

\[ \begin{align*} ht[i]&\ge lcp(i,j+1)\\ &=lcp(i-1,j)-1\\ &=ht\big[rk[i-1]\big]-1 \end{align*} \]

根据引理 \(3\)，我们只需要依次枚举 \(i\in[1,n]\)，然后从 \(ht\big[rk[i-1]\big]-1\) 开始暴力扩展，得到 \(ht\big[rk[i]\big]\)。增量不超过 \(2n\)，因此总时间复杂度为 \(O(n)\)。

考虑边界条件 \(rk[i]=1\)。此时必有 \(sa\big[rk[i-1]-1\big]=n\)，否则 \(sa[rk[i-1]-1]+1\) 是比 \(i\) 后缀字典序更小的另一个后缀。因此 \(ht\big[rk[i-1]\big]\le 1\)。我们只需要在 \(rk[i]=1\) 时直接跳过即可。

void get_height() {
    int k = 0;
    for(int i = 1; i <= n; i++) {
        if(rk[i] == 1) continue;
        k -= (bool)k;
        int j = sa[rk[i] - 1], lim = min(n - i + 1, n - j + 1);
        while(k < lim && a[i + k] == a[j + k]) ++k;
        ht[rk[i]] = k;
    }
}

例题

P3809 【模板】后缀排序

输出后缀数组即可。

模板代码 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<iostream>
using namespace std;
const int N = 1e6 + 10;

int n, m;
string s;

int sa[N], rk[N], tp[N], cnt[N];

void sort() {
    for(int i = 1; i <= m; i++) cnt[i] = 0;
    for(int i = 1; i <= n; i++) ++cnt[rk[i]];
    for(int i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
    for(int i = n; i >= 1; i--) sa[cnt[rk[tp[i]]]--] = tp[i];
}

void suf_sort() {
    for(int i = 1; i <= n; i++) rk[i] = s[i];
    for(int i = 1; i <= n; i++) tp[i] = i;
    sort();
    int p = 0;
    for(int w = 1; w <= n; w <<= 1) {
        p = 0;
        for(int i = n - w + 1; i <= n; i++) tp[++p] = i;
        for(int i = 1; i <= n; i++) {
            if(sa[i] > w) tp[++p] = sa[i] - w;
        }
        sort();
        swap(rk, tp);
        rk[sa[1]] = 1;
        for(int i = 2; i <= n; i++) {
            if(tp[sa[i - 1]] == tp[sa[i]] && tp[sa[i - 1] + w] == tp[sa[i] + w]) {
                rk[sa[i]] = rk[sa[i - 1]];
            } else rk[sa[i]] = rk[sa[i - 1]] + 1;
        }
        if(rk[sa[n]] >= n) break;
        m = rk[sa[n]];
    }
}

int main() {

    cin >> s;
    n = s.size();
    m = 127;
    s = '#' + s;

    suf_sort();

    for(int i = 1; i <= n; i++) {
        cout << sa[i] << ' ';
    }
    cout << endl;

    return 0;
}

Y9-1 不可重叠串

题意

给出长度为 \(n\) 的数字串，求最大相似子串长度，如果没有输出 \(0\)。

相似子串定义为：

  • 两个不重叠的子串，差是一个定值；
  • 长度 \(\ge 5\)；

先对序列进行差分，问题转换为：求两个不重叠的相等子串长度的最大值。

两个相等的子串可以看作是两个后缀的 \(lcp\)，就是 \(height\) 数组上的一段区间。然而“不重叠”条件还限制了两个后缀不能离太近。

我们考虑二分答案。先将所有 \(ht[i]\ge mid\) 的位置筛选出来，标记为 \(1\)。如果存在一段连续 \(1\) 的区间中，包含两个相距足够远的后缀，则判定成功。我们只需要记录一段区间中最靠前的后缀和最靠后的后缀即可。

代码 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include<iostream>
#include<iomanip>
using namespace std;
const int N = 2e4 + 10;
const int INF = (int)0x3f3f3f3f3f3f3f3f;

int n, m;
int a[N];

int sa[N], rk[N], tp[N], cnt[N];
int ht[N];

void sort() {
    for(int i = 1; i <= m; i++) cnt[i] = 0;
    for(int i = 1; i <= n; i++) ++cnt[rk[i]];
    for(int i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
    for(int i = n; i >= 1; i--) sa[cnt[rk[tp[i]]]--] = tp[i];
}

void get_sa() {
    m = 180;
    for(int i = 1; i <= n; i++) rk[i] = a[i];
    for(int i = 1; i <= n; i++) tp[i] = i;
    sort();
    for(int w = 1, p; w <= n; w <<= 1) {
        p = 0;
        for(int i = n - w + 1; i <= n; i++) tp[++p] = i;
        for(int i = 1; i <= n; i++) {
            if(sa[i] > w) tp[++p] = sa[i] - w;
        }
        sort();
        for(int i = 1; i <= n; i++) tp[i] = rk[i];
        rk[sa[1]] = 1;
        for(int i = 2; i <= n; i++) {
            if(tp[sa[i]] == tp[sa[i - 1]] && tp[sa[i] + w] == tp[sa[i - 1] + w]) {
                rk[sa[i]] = rk[sa[i - 1]];
            } else rk[sa[i]] = rk[sa[i - 1]] + 1;
        }
        if(rk[sa[n]] == n) break;
        m = rk[sa[n]];
    }
}

void get_height() {
    int k = 0;
    for(int i = 1; i <= n; i++) {
        if(rk[i] == 1) {
            if(k > 1) throw -1;
            continue;
        }
        k -= (bool)k;
        int j = sa[rk[i] - 1], lim = min(n - i + 1, n - j + 1);
        while(k < lim && a[i + k] == a[j + k]) ++k;
        ht[rk[i]] = k;
    }
}

bool check(int lim) {
    int mn = INF, mx = 0;
    for(int i = 2; i <= n; i++) {
        if(ht[i] >= lim) {
            mn = min(mn, min(sa[i], sa[i - 1]));
            mx = max(mx, max(sa[i], sa[i - 1]));
            if(mx - mn > lim) return true;
        } else {
            mn = INF;
            mx = 0;
        }
    }
    return false;
}

int main() {

    while(cin >> n) {
        if(!n) break;
        for(int i = 1; i <= n; i++) cin >> a[i];
        for(int i = 1; i <= n - 1; i++) a[i] = a[i + 1] - a[i] + 90;
        --n;

        get_sa();
        get_height();

        int l = 0, r = n;
        while(l < r) {
            int mid = (l + r + 1) >> 1;
            if(check(mid)) l = mid;
            else r = mid - 1;
        }

        if(l < 4) cout << 0 << endl;
        else cout << l + 1 << endl;
    }

    return 0;
}

Y9-2 最长公共子串

题意

给定 \(n\) 个字符串 \(s_i\)，求一个最长的字符串 \(t\)，满足 \(t\) 在所有 \(n\) 个串或它们的翻转中出现过。

\(\sum|s_i|\le 10^4\)

先将 \(n\) 个串和它们的翻转全部拼在一起，中间加分隔符，每个字符串对应的区域有不同的颜色，形成长串 \(s\)。问题转化为：在 \(s\) 中选出 \(n\) 个指针 \(p_i\)，每个颜色区域恰有一个指针。\(lcp\big\{[p_i,n]\big\}\) 就是一个合法的公共子串。

显然，\(lcp\big\{[p_i,n]\big\}\) 对应 \(height\) 数组中的一段区间，并且这段区间应该包含全部 \(n\) 种颜色。同时我们希望这段区间尽可能小，这样 \(lcp\) 才会最大。

考虑使用桶和双指针维护出：所有包含 \(n\) 种颜色的极小区间；再使用单调队列维护滑窗最值即可。

注意：\(lcp\) 不能跨过任何分隔符。因此需要在求出 \(height\) 后，把跨过分隔符的部分全部切除。

技巧

多个不同后缀的 \(lcp\) 会在 \(s\) 中重复出现多次。后缀 \(lcp\) 等价于 \(height\) 数组中的一段区间。通过限制后缀的位置，可以限制重复子串的位置。

代码 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include<iostream>
#include<iomanip>
#include<algorithm>
using namespace std;
const int N = 3e4 + 10;

int T;
int n, m, k, ans;
int col[N], dis[N];
string s;

int sa[N], rk[N], ht[N];

namespace SA {

    int cnt[N], tp[N];
    void sort() {
        for(int i = 1; i <= m; i++) cnt[i] = 0;
        for(int i = 1; i <= n; i++) ++cnt[rk[i]];
        for(int i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
        for(int i = n; i >= 1; i--) sa[cnt[rk[tp[i]]]--] = tp[i];
    }

    void get_SA() {
        m = 128;
        for(int i = 1; i <= n; i++) rk[i] = s[i];
        for(int i = 1; i <= n; i++) tp[i] = i;
        sort();
        for(int w = 1, p; w < n; w <<= 1) {
            p = 0;
            for(int i = n - w + 1; i <= n; i++) tp[++p] = i;
            for(int i = 1; i <= n; i++) {
                if(sa[i] > w) tp[++p] = sa[i] - w;
            }
            sort();
            for(int i = 1; i <= n; i++) tp[i] = rk[i];
            rk[sa[1]] = 1;
            for(int i = 2; i <= n; i++) {
                if(tp[sa[i]] == tp[sa[i - 1]] && tp[sa[i] + w] == tp[sa[i - 1] + w]) {
                    rk[sa[i]] = rk[sa[i - 1]];
                } else rk[sa[i]] = rk[sa[i - 1]] + 1;
            }
            if(rk[sa[n]] == n) break;
            m = rk[sa[n]];
        }
    }

    void get_height() {
        int p = 0;
        for(int i = 1; i <= n; i++) {
            if(rk[i] == 1) continue;
            p -= (bool)p;
            int j = sa[rk[i] - 1], lim = min(n - i + 1, n - j + 1);
            while(p < lim && s[i + p] == s[j + p]) ++p;
            ht[rk[i]] = p;
        }
        for(int i = 2; i <= n; i++) {
            ht[i] = min(ht[i], min(dis[sa[i - 1]], dis[sa[i]]));
        }
    }

}

int cnt[N], cc;
int que[N], hd, tl;

void work() {

    for(int i = 0; i < N; i++) sa[i] = ht[i] = rk[i] = col[i] = dis[i] = 0;
    for(int i = 0; i < N; i++) cnt[i] = 0;
    cc = 0;

    cin >> k;
    s = "#";
    for(int i = 1; i <= k; i++) {
        string tmp;
        cin >> tmp;
        for(int j = 0; j < tmp.size(); j++) dis[s.size() + j] = tmp.size() - j;
        for(int j = 0; j < tmp.size(); j++) col[s.size() + j] = i;
        s = s + tmp + '$';
        for(int j = 0; j < tmp.size(); j++) dis[s.size() + j] = tmp.size() - j;
        for(int j = 0; j < tmp.size(); j++) col[s.size() + j] = i;
        reverse(tmp.begin(), tmp.end());
        s = s + tmp + '#';
    }

    if(k == 1) {
        cout << (s.size() - 3) / 2 << '\n';
        return;
    }

    n = s.size() - 1;
    SA::get_SA();
    SA::get_height();

    ans = 0;
    hd = 1, tl = 0;
    for(int l = 1, r = 1; r <= n; r++) {
        if(r > 1) {
            while(hd <= tl && ht[que[tl]] >= ht[r]) --tl;
            que[++tl] = r;
        }
        if(col[sa[r]]) ++cnt[col[sa[r]]];
        if(cnt[col[sa[r]]] == 1) ++cc;
        while(cc == k && (!col[sa[l]] || cnt[col[sa[l]]] > 1)) {
            --cnt[col[sa[l]]];
            ++l;
        }
        while(hd <= tl && que[hd] <= l) ++hd;
        if(cc == k) ans = max(ans, ht[que[hd]]);
    }

    cout << ans << '\n';

}

int main() {

    cin >> T;
    while(T--) work();

    return 0;
}

Y9-3 连续重复子串

题意

字符串的重复次数定义为最大数 \(R\)，表示可以将该字符串划分为 \(R\) 个相同的连续子串。

给定一个字符串 \(s\)，求它重复次数最多的子串，要求字典序最小。

重复次数为 \(1\) 的情况比较特殊，我们分开考虑。这种情况直接选择一个字典序最小的字符一定最优。现在我们只考虑重复次数 \(\ge 2\) 次的情况。

考虑后缀 \(i\) 和循环节长度 \(R\)，\(\frac{lcp(i,i+R)+R}{R}\) 是从 \(i\) 开始的，循环节长度为 \(R\) 的最大重复次数。

重复次数（或循环节长度）不具有单调性，不能进行二分，只能枚举。如果直接枚举后缀 \(i\) 和循环节长度 \(R\)，时间复杂度将达到 \(O(n^2)\)。

注意到这种朴素的枚举方式会围绕一个重复串反复查询多次，浪费大量时间。我们希望尽可能拓展一次查询能覆盖到的范围，这样就可以减少查询次数。

朴素的一次查询 \((i,R)\) 能覆盖的范围和查询的结果也有关。如果恰好只探测到了 \(2\) 次重复，则覆盖范围只有 \(i\) 一个点，覆盖范围的最小值没有保证。

注意到：若一次查询 \((i,R)\) 还可以向左拓展到极长位置，则至少可以覆盖起始位置 \(j\in (i-R,i]\) 的所有重复串。这样，我们只需要查询 \(\frac{n}{R}\) 次就可以了。总时间复杂度是一个调和级数，结果为 \(O(n\ln n)\)。

具体的，我们查询所有 \((kR,R)\)，其中 \(k\in \N\)，每次查询都向左右两个方向同时扩展，就可以查询到所有同时覆盖 \(i,i+R\) 两个节点的重复串。

对于 \(\frac{lcp(i,i+R)+R}{R}\) 不整除的情况，重复串被允许有一定范围的滑动。我们使用第二个 st 表来维护这段范围内字典序最小的串。后缀数组可以快速比较两个子串的字典序大小。

代码 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
const int LOGN = 19;

string s;

int n, m;
int lg[N];
int sa[2][N], rk[2][N], tp[N], cnt[N];
int mn[2][LOGN][N];

void sort(int *sa, int *rk, int *tp, int *cnt) {
    for(int i = 1; i <= m; i++) cnt[i] = 0;
    for(int i = 1; i <= n; i++) ++cnt[rk[i]];
    for(int i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
    for(int i = n; i >= 1; i--) sa[cnt[rk[tp[i]]]--] = tp[i];
}

void get_SA(int *sa, int *rk, int *tp, int *cnt) {
    m = 127;
    for(int i = 1; i <= n; i++) rk[i] = s[i];
    for(int i = 1; i <= n; i++) tp[i] = i;
    sort(sa, rk, tp, cnt);
    for(int w = 1, p; w < n; w <<= 1) {
        p = 0;
        for(int i = n - w + 1; i <= n; i++) tp[++p] = i;
        for(int i = 1; i <= n; i++) {
            if(sa[i] > w) tp[++p] = sa[i] - w;
        }
        sort(sa, rk, tp, cnt);
        for(int i = 1; i <= n; i++) tp[i] = rk[i];
        rk[sa[1]] = 1;
        for(int i = 2; i <= n; i++) {
            if(tp[sa[i]] == tp[sa[i - 1]] && tp[sa[i] + w] == tp[sa[i - 1] + w]) {
                rk[sa[i]] = rk[sa[i - 1]];
            } else rk[sa[i]] = rk[sa[i - 1]] + 1;
        }
        if(rk[sa[n]] == n) break;
        m = rk[sa[n]];
    }
}

void get_height(int *ht, int *sa, int *rk) {
    int k = 0;
    for(int i = 1; i <= n; i++) {
        if(rk[i] == 1) continue;
        k -= (bool)k;
        int j = sa[rk[i] - 1], lim = min(n - i + 1, n - j + 1);
        while(k < lim && s[i + k] == s[j + k]) ++k;
        ht[rk[i]] = k;
    }
}

void get_st(int t) {
    for(int w = 1; w < LOGN; w++) {
        for(int i = 1; i + (1 << w) - 1 <= n; i++) {
            mn[t][w][i] = min(mn[t][w - 1][i], mn[t][w - 1][i + ( 1 << (w - 1) )]);
        }
    }
}

// 查询 lcp
int query(int t, int x, int y) {
    if(t) { x = n - x + 1; y = n - y + 1; }
    if(x == y) return n - x + 1;
    x = rk[t][x], y = rk[t][y];
    if(x > y) swap(x, y);
    int d = lg[y - (++x) + 1];
    return min(mn[t][d][x], mn[t][d][y - (1 << d) + 1]);
}

// 比较字典序
bool cmp(int l1, int r1, int l2, int r2) {
    if(query(0, l1, l2) >= min(r1 - l1 + 1, r2 - l2 + 1)) return (r1 - l1 + 1) < (r2 - l2 + 1);
    return rk[0][l1] < rk[0][l2];
}

int rk_mn[LOGN][N];

void get_rk_mn() {
    for(int i = 1; i <= n; i++) rk_mn[0][i] = i;
    for(int w = 1; w < LOGN; w++) {
        for(int i = 1; i + (1 << w) - 1 <= n; i++) {
            int a = rk_mn[w - 1][i], b = rk_mn[w - 1][i + ( 1 << (w - 1) )];
            rk_mn[w][i] = rk[0][a] < rk[0][b] ? a : b;
        }
    }
}

int query_rk_mn(int l, int r) {
    if(l > r) swap(l, r);
    int d = lg[r - l + 1];
    int a = rk_mn[d][l], b = rk_mn[d][r - (1 << d) + 1];
    return rk[0][a] < rk[0][b] ? a : b;
}

string work() {
    n = s.size();
    s = '#' + s;

    get_SA(sa[0], rk[0], tp, cnt);
    get_height(mn[0][0], sa[0], rk[0]);
    get_st(0);

    reverse(++s.begin(), s.end());
    get_SA(sa[1], rk[1], tp, cnt);
    get_height(mn[1][0], sa[1], rk[1]);
    get_st(1);

    reverse(++s.begin(), s.end());

    get_rk_mn();

    int ans = 0, al, ar;
    for(int i = 1; i <= n - 1; i++) {
        for(int j = i; j + i <= n; j += i) {
            int k = j + i;
            if(s[j] != s[k]) continue;
            int t1 = query(1, j, k), t2 = query(0, j, k);
            int lcp = t1 + t2 - 1;
            if(lcp < i) continue;
            lcp += i;
            int res = lcp / i;
            if(res > ans) {
                ans = res;
                al = query_rk_mn(j - t1 + 1, j + t2 + i - res * i);
                ar = al + res * i - 1;
            } else if(res == ans) {
                int nl = query_rk_mn(j - t1 + 1, j + t2 + i - res * i);
                int nr = nl + res * i - 1;
                if(cmp(nl, nr, al, ar)) { al = nl; ar = nr; }
            }
            j += max(0, res - 1) * i;
        }
    }

    if(!ans) return (string){s[sa[0][1]]};
    return s.substr(al, ar - al + 1);
}

int main() {

    for(int i = 2; i < N; i++) lg[i] = lg[i >> 1] + 1;

    while(cin >> s) {
        static int i = 0;
        if(s == "#") break;
        cout << "Case " << ++i << ": " << work() << '\n';
    }

    return 0;
}