跳转至

后缀数组（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\) 的区间中，包含两个相距足够远的后缀，则判定成功。我们只需要记录一段区间中最靠前的后缀和最靠后的后缀即可。

转化为区间最小值

对于一个字符串 \(s\)，一些后缀（可以超过 \(2\) 个）的 \(\operatorname{lcp}\) 等价于 height 数组上的一段区间最小值。这是 SA 的一种很常见的手段。

然后，我们就可以使用单调栈统计贡献，使用双指针、可行位置染色等方法求解最优化问题。

代码 
 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_1+rev(s_1)+s_2+rev(s_2)+\cdots+s_n+rev(s_n) \]

记得在中间加分隔符。

现在问题转化为，在 \(s\) 中选择一个子串，这个子串在每个 \(s_i\) 对应的区域内都至少出现一次。也即：画出 \(n\) 个指针 \(p_i\)，每个颜色区域恰有一个指针，最大化 \(\operatorname{lcp}\big\{s[p_i,n]\big\}\)。

由于后缀 \(\operatorname{lcp}\) 对应于 height 数组中的一段区间；问题又转化为：在 height 数组上选择一段区间，包含全部 \(n\) 种颜色，最大化区间最小值。直接双指针即可。

注意：\(\operatorname{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;
}

Y9-4 后缀求和

题意

给定一个长度为 \(n\) 的字符串 \(s\)，下标从 \(1\) 开始，保证只包含小写字母。

现在有若干组询问，对于每一个询问，我们给出若干个后缀（以其在 \(s\) 中出现的起始位置来表示），求这些后缀两两之间 \(\operatorname{lcp}\) 的长度之和。

\(n\le 5\times 10^5\)

代码 
  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
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cassert>
#define ll long long

using namespace std;
const int N = 5e5 + 10;
const int K = 3e6 + 10;
const int LOGN = 20;

int n, q;
char s[N];

namespace SA {
    int m;
    int sa[N], rk[N], tp[N], cnt[N], 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 = 30;
        for(int i = 1; i <= n; i++) rk[i] = s[i] - 'a' + 1;
        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;
            }
            m = rk[sa[n]];
            if(m == n) break;
        }
    }
    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];
            while(i + k <= n && j + k <= n && s[i + k] == s[j + k]) ++k;
            ht[rk[i]] = k;
        }
    }
    int mn[LOGN][N], lg[N];
    void init_st() {
        for(int i = 2; i <= n; i++) lg[i] = lg[i >> 1] + 1;
        for(int i = 1; i <= n; i++) mn[0][i] = ht[i];
        for(int k = 1; k < LOGN; k++) {
            for(int i = 1; i + (1 << k) - 1 <= n; i++) {
                mn[k][i] = min(mn[k - 1][i], mn[k - 1][i + (1 << (k - 1))]);
            }
        }
    }
    int query(int x, int y) {
        if(x == y) return n - x + 1;
        x = rk[x], y = rk[y];
        if(x > y) swap(x, y);
        ++x;
        int d = lg[y - x + 1];
        return min(mn[d][x], mn[d][y - (1 << d) + 1]);
    }
}

int k;
int p[K], w[N];
int lm[N], rm[N];
int sta[N], top;

ll ans;

bool cmp_rk(int a, int b) {
    return SA::rk[a] < SA::rk[b];
}

int main() {

    cin >> n >> q;
    cin >> (s + 1);

    SA::get_sa();
    SA::get_height();
    SA::init_st();

    while(q--) {
        ans = 0;
        cin >> k;
        for(int i = 1; i <= k; i++) cin >> p[i];
        sort(p + 1, p + 1 + k, cmp_rk);
        k = unique(p + 1, p + 1 + k) - (p + 1);
        --k;
        for(int i = 1; i <= k; i++) {
            w[i] = SA::query(p[i], p[i + 1]);
        }
        top = 0;
        sta[top] = 0;
        for(int i = 1; i <= k; i++) {
            while(top && w[i] < w[sta[top]]) --top;
            lm[i] = sta[top];
            sta[++top] = i;
        }
        top = 0;
        sta[top] = k + 1;
        for(int i = k; i >= 1; i--) {
            while(top && w[i] <= w[sta[top]]) --top;
            rm[i] = sta[top];
            sta[++top] = i;
        }
        for(int i = 1; i <= k; i++)s {
            ans += (ll)w[i] * (i - lm[i]) * (rm[i] - i);
        }
        cout << ans << '\n';
    }

    return 0;
}

Y9-5 可重叠子串

题意

给出长度为 \(n\) 的数字串，找出出现至少 \(k\) 次的可重叠的最长子串的长度。

代码 
 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
#include<iostream>
#include<iomanip>
using namespace std;
const int N = 2e4 + 10;
const int M = 1e6 + 10;

int n, k;
int a[N];

namespace SA {
    int m;
    int sa[N], rk[N], tp[N], cnt[M], 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 = M - 10;
        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;
            }
            m = rk[sa[n]];
            if(m == n) break;
        }
    }
    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];
            while(i + k <= n && j + k <= n && a[i + k] == a[j + k]) ++k;
            ht[rk[i]] = k;
        }
    }
}

using namespace SA;

int ans = 0;
int que[N], hd, tl;

int main() {

    cin >> n >> k;
    for(int i = 1; i <= n; i++) cin >> a[i];

    get_sa();
    get_height();

    hd = 1, tl = 0;
    for(int i = 2; i <= n; i++) {
        while(hd <= tl && que[hd] <= i - k + 1) ++hd;
        while(hd <= tl && ht[i] <= ht[que[tl]]) --tl;
        que[++tl] = i;
        if(i >= k) ans = max(ans, ht[que[hd]]);
    }

    cout << ans << endl;

    return 0;
}

Y9-7 公共串计数

题意

给定两个字符串 \(s_1\) 和 \(s_2\)，长度分别为 \(n_1\) 和 \(n_2\)；给定常数 \(k\)，求有序数对 \((x,y)\) 的数量，满足：

  • \(x\in [1,n_1],\ y\in [1,n_2]\)；
  • \(\operatorname{lcp}(s_1[x\sim n_1],s_2[y\sim n_2])\ge k\)；

先将两个字符串拼接起来，求后缀数组；记 \(col[i]\) 表示 \(sa[i]\) 位置是 \(s_1\) 还是 \(s_2\)。考虑 height 数组中的一个值 \(ht[i]\) 能贡献到的区间 \([l_i,r_i]\)，对于一对 \(i\in [l_i,i],\ j\in [i+1,r_i+1]\) 且 \(col[i]\ne col[j]\)，将会贡献 \(\max(0, ht[i]-k)\) 对合法的 \((x,y)\)。使用单调栈预处理 \(l_i,r_i\) 即可，时间复杂度 \(O(n\log n)\)，瓶颈在 SA。

代码 
  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
#include<iostream>
#include<iomanip>
#include<cassert>
#define print(a) cout << setw(8) << #a": "; for(int i = 1; i <= n; i++) { cout << setw(2) << a << ' '; } cout << endl;

// #define int long long
#define ll long long

using namespace std;
const int N = 2e5 + 10;

int k;
char tmp1[N], tmp2[N];
string ss1, ss2, s;

int n, m;

namespace SA {
    int m;
    int sa[N], rk[N], tp[N], cnt[N], 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 = 127;
        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;
            }
            m = rk[sa[n]];
            if(m == n) break;
        }
    }
    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];
            while(i + k <= n && j + k <= n && s[i + k] == s[j + k]) ++k;
            ht[rk[i]] = k;
        }
    }
}

using SA::get_sa;
using SA::get_height;
using SA::sa;
using SA::ht;
using SA::rk;

int sta[N], top;
int lm[N], rm[N];

ll ans;

ll s0[N], s1[N];

inline ll q0(int l, int r) { return s0[r] - s0[l - 1]; }
inline ll q1(int l, int r) { return s1[r] - s1[l - 1]; }

void init() {
    ans = 0;
    for(int i = 0; i <= n + 5; i++) {
        s0[i] = s1[i] = sta[i] = lm[i] = rm[i] = 0;
    }
}

void work() {

    init();

    ss1 = (string)tmp1;
    ss2 = (string)tmp2;

    s = "#" + ss1 + "#" + ss2;
    m = ss1.size() + 1;
    n = s.size() - 1;

    for(int i = 1; i <= n; i++) {
        if(!('a' <= s[i] && s[i] <= 'z' || s[i] == '#')) {
            cout << n << ' ' << m << endl;
            cout << i << ' ' << (int)s[i] << endl;
            exit(-1);
        }
    }

    get_sa();
    get_height();
    for(int i = 1; i <= n; i++) {
        s0[i] = s0[i - 1] + (sa[i] < m);
        s1[i] = s1[i - 1] + (sa[i] > m);
    }
    sta[top = 0] = 1;
    for(int i = 2; i <= n; i++) {
        while(top && ht[i] < ht[sta[top]]) --top;
        lm[i] = sta[top];
        sta[++top] = i;
    }
    sta[top = 0] = n + 1;
    for(int i = n; i >= 2; i--) {
        while(top && ht[i] <= ht[sta[top]]) --top;
        rm[i] = sta[top];
        sta[++top] = i;
    }
    for(int i = 2; i <= n; i++) {
        if(ht[i] >= k) {
            ans += q0(lm[i], i - 1) * q1(i, rm[i] - 1) * (ht[i] - k + 1);
            ans += q1(lm[i], i - 1) * q0(i, rm[i] - 1) * (ht[i] - k + 1);
        }
    }
    cout << ans << '\n';
}

int main() {

    while(cin >> k) {
        if(!k) break;
        cin >> tmp1 >> tmp2;
        work();
    }

    return 0;
}

Y9-8 区间颠倒

题意

给定一个序列 \(s\)，请你找出 \(2\) 个划分点 \(i,j\)（\(1\le i<j<n\)），然后将区间 \([1,i],[i+1,j],[j+1,n]\) 分别翻转，最小化 \(s'\) 的字典序。

保证 \(s[1]\) 严格大于 \(s\) 中的其他所有数。

先将 \(s\) 整个翻转，问题等价于找到 \(i,j\) 然后将 \([1,i]\) 和 \([j+1,n]\) 交换，最小化字典序。

先将所有后缀排序，容易发现由于 \(s[n]\) 是最大值，因此后缀排序不会出现两个串具有前缀关系，因此后缀排序的结果是“严格”的。此时，找到字典序最小的后缀，将它交换到前面，一定更优。

接下来，子问题形如找到 \(s'\) 的一个划分点，将前后两段交换，最小化字典序。注意到将 \(s'\leftarrow s'+s'\) 之后，答案一定是 \(s'\) 中一段长度为 \(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
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
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 4e5 + 10;

namespace SA {

    int n, m;
    int a[N];

    int sa[N], rk[N], 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(int _n, int _a[]) {
        n = _n;
        for(int i = 1; i <= n; i++) a[i] = _a[i];
        m = N - 5;
        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; w < n; w <<= 1) {
            int 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;
            }
        }
    }

}

int n, k1, k2, tmp;
int a[N], b[N];

int nn;
int num[N];

void lisanhua() {
    for(int i = 1; i <= n; i++) num[++nn] = a[i];
    sort(num + 1, num + 1 + nn);
    nn = unique(num + 1, num + 1 + nn) - (num + 1);
    for(int i = 1; i <= n; i++) a[i] = lower_bound(num + 1, num + 1 + nn, a[i]) - num;
}

int main() {

    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];

    reverse(a + 1, a + 1 + n);
    for(int i = 1; i <= n; i++) b[i] = a[i];
    lisanhua();
    SA::get_SA(n, a);

    tmp = 1;
    while(SA::sa[tmp] <= 2) ++tmp;
    k1 = SA::sa[tmp] - 1;

    for(int i = 1; i <= k1; i++) a[i + k1] = a[i];
    SA::get_SA(2 * k1, a);

    tmp = 1;
    while(SA::sa[tmp] > k1 || SA::sa[tmp] == 1) ++tmp;
    k2 = SA::sa[tmp] - 1;

    for(int i = k1 + 1; i <= n; i++) cout << b[i] << '\n';
    for(int i = k2 + 1; i <= k1; i++) cout << b[i] << '\n';
    for(int i = 1; i <= k2; i++) cout << b[i] << '\n';

    return 0;
}