后缀数组
/ / 阅读耗时 93 分钟 后缀数组是一类应用在字符串中的算法。本文改自这篇博客，下面的代码基于这个题目。
后缀
在KMP匹配算法中已经提及。对于字符串abcde，它的后缀为abcde、bcde、…、de、e，这里的后缀是可以含本身的。
后缀字典序
字典序排列是两个字符串之间进行排列比较的手段，它的做法是从左到右依次比较两个字符串的对应位置，ascii码较小的一个字典序更小。如果到某一个字符串已经比较到结尾，则长度较小的一个字典序更小。例如ab<ac，ab<abc。
后缀数组及其求法
首先认识什么是后缀数组。对于一个字符串的所有后缀，我们将它们按照字典序从小到大排列，并开一个数组sa使得sa[i]为排名为i的后缀在原字符串中的起始位置（为简便起见，在下文中称为位置。排名从1开始，原字符串下标也从1开始），这个sa数组就称为后缀数组（Suffix Array ，SA）。
由于后缀的长度各不相同，它们的字典序序号必然各不相同。此时构造一个数组rk为sa数组的反射，即rk[i]表示位置为i的后缀的排名。
下面探讨后缀数组的构造方法，这里只介绍倍增方法。
一种简单粗暴的方法就是直接快排，时间复杂度为$O(n^2logn)$，显然不可行，倍增算法可以将其优化到$O(nlogn)$复杂度。
倍增的思想：将字符串看成两部分：前半部分和后半部分。这样字符串就成为了一个二元组，前半部分为第一关键字，后半部分为第二关键字。如果我们已经求出第一关键字的排名，并求出了第二关键字的相对位置，那么总的排序序列就可以被求出了。之后再将前后两部分看成一个整体，作为下一次运算的前半部分，依次递归进行。
在这里，采用数组tp来当做第二关键字，它的作用与sa类似：tp[i]表示第二关键字排名为i的后缀的位置。第一关键字用rk数组来充当。
首先第一步：将每一个后缀按首位字符排序，第一关键字为首字符ascii码，第二关键字为首字符的下标。这里的第二关键字就是tp数组，事实上只要tp数组构成{1..n}->{1..n}的双射即可。1
for (int i = 1; i <= n; i++)rk[i] = op[i] - '0', tp[i] = n - i + 1;//op是原字符串
下面进行排序，排序即是根据rk和tp数组对sa数组进行修改。对于排序的详细操作留在文末，继续看倍增操作。
到这里sa中已经记录了按照首字符排列的序列信息，下面考虑倍增。1
2
3for (int w = 1, p = 0; p < n;w <<= 1) {
//...
}
w是指目前已经按照w大小进行排序（比如一开始只按首字符排序，故w=1），p暂且不用管它。每一次循环之后都需要w自乘2。1
2
3p = 0;
for (int i = 1; i <= w; i++)tp[++p] = n - w + i;
for (int i = 1; i <= n; i++)if (sa[i] > w)tp[++p] = sa[i] - w;
上面是循环体中的第一部分代码，这里p用来记录排名。这三行代码的作用是求出第二关键字的相对排名，根据倍增思想，充当第二关键字的字符串长度也应为w。对于一个后缀，我们已经求出了它前w的字符作为关键字的排名，现在要求再向后w个字符的相对排名。这时可以发现有些后缀是没有第二关键字的，比如位置为n、n-1、…、n-w+1的后缀就没有第二关键字。这里的没有是指完全没有，部分没有的后缀不计入其中。对于这些没有第二关键字的后缀，根据字典序的定义，它们在按照第二关键字排序时应该排到前面，因次第一个for循环将末尾那些不存在第二关键字的后缀首先进行了排名。
第二步是很精妙的操作。容易发现位置为i的后缀的第二关键字恰好就是位置为i+w的后缀的第一关键字，而后者的相对位置已经确定，那么不妨就根据这个关系更新第二关键字的相对位置。第二个for循环中，从排名第1的后缀开始遍历，凡是满足sa[i]>w的后缀（sa[i]>w表示这个后缀的前面必有一个第二关键字与它第一关键字相同的后缀），更新它的第二关键字排名。
这样第二关键字的tp数组也被求出，在利用已经求出的rk数组，可以再进行一步排序来更新sa，排序的详细步骤仍然留到最后。
但是下一次倍增中需要rk数组，rk数组还没有更新，因此下面需要更新rk数组。
上面已经提到，rk数组是sa数组的反射，其实这种说法并不准确。在整个过程结束后，rk数组确实是sa数组的反射，但在求解过程中并不是。sa数组储存排名为i的后缀的位置，这是一个从排名到后缀的双射。也就是说，对于我们目前的排序关键字，可能存在“完全相同”的两个后缀，它们在sa数组中是得不到体现的（虽然排名一定靠着），在更新rk数组时要留意这一点。
更新rk数组时需要留意相同的后缀，并给它们相同的排名，即两个后缀的rk值可能相同。容易发现，当所有后缀的rk值两两不同时，说明后缀数组构造完毕，此时结束循环，这也是判断后缀数组构造完成的指标。
判定两个后缀相同可以用如下方法判定：第一关键字排名（rk）值相同并且第二关键字排名（rk）值相同，这样就可以判定它们第一关键字和第二关键字都相同，两个后缀在当前关键字下便相同。这里需要上一次的rk数组，但同时又要更新rk数组，为了防止混淆，我们将rk数组复制到tp中，此时tp数组已经没用了。1
for (int i = 1; i <= n; i++)tp[i] = rk[i];
下面是更新rk的核心代码：1
2
3
4rk[sa[1]] = p = 1;//初始化
for (int i = 2; i <= n; i++) {
rk[sa[i]] = (tp[sa[i - 1]] == tp[sa[i]] && tp[sa[i - 1] + w] == tp[sa[i] + w]) ? p : ++p;
}
这里p的意义是记录互不相同的排名数量，当p=n时所有后缀排名互不相同，结束循环，这也是上文中for循环的终止条件。
下面的for循环利用相同后缀排名必相同的性质，将每一个后缀都与前一个后缀进行比较，如果第一关键字排名相同并且第二关键字排名相同则与上一个后缀的排名相同，否则分配一个新排名。这里的第二关键字排名仍然用上文所说的性质。
基数排序
现在可以来探讨排序的方法，这里采用基数排序。1
2
3
4
5
6void mySort() {
for (int i = 0; i <= M; i++)tax[i] = 0;
for (int i = 1; i <= n; i++)tax[rk[i]]++;
for (int i = 1; i <= M; i++)tax[i] += tax[i - 1];
for (int i = n; i >= 1; i--)sa[tax[rk[tp[i]]]--] = tp[i];
}
tax是基数排序用的桶，M是第一关键字的最大取值，由于第一关键字是排名信息，可以设置成1e6+5（按照题目条件）。第一个for循环将桶清空。
第二个for循环将第一关键字的信息放入桶中，统计数目。
第三个for循环求前缀和，这是为了方便求排名。
第四个for循环较难理解。倒序遍历后缀，由于已经求了前缀和，这时的tax值就是排名，之后用自减一的方式将其从桶中取出。
另外这里有一处优化。M由于是第一关键字的最大值，因此可以根据每一次循环的p值来修改M，以降低时间复杂度。注意一开始第一关键字的最大值是’z’-‘0’。
这样就得到了求后缀数组的完整步骤，下面给出模板题代码：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
using namespace std;
int n, sa[N], tp[N], rk[N], tax[N], M;
char op[N];
inline void mySort() {
for (int i = 0; i <= M; i++)tax[i] = 0;
for (int i = 1; i <= n; i++)tax[rk[i]]++;
for (int i = 1; i <= M; i++)tax[i] += tax[i - 1];
for (int i = n; i >= 1; i--)sa[tax[rk[tp[i]]]--] = tp[i];
}
inline void solve() {
M = 80;
for (int i = 1; i <= n; i++)rk[i] = op[i] - '0' + 1, tp[i] = i;
mySort();
for (int w = 1, p = 0; p < n; M = p, w <<= 1) {
p = 0;
for (int i = 1; i <= w; i++)tp[++p] = n - w + i;
for (int i = 1; i <= n; i++)if (sa[i] > w)tp[++p] = sa[i] - w;
mySort();
for (int i = 1; i <= n; i++)tp[i] = rk[i];
rk[sa[1]] = p = 1;
for (int i = 2; i <= n; i++) {
rk[sa[i]] = (tp[sa[i - 1]] == tp[sa[i]] && tp[sa[i - 1] + w] == tp[sa[i] + w]) ? p : ++p;
}
}
for (int i = 1; i <= n; i++) {
cout << sa[i] << " ";
}
}
int main() {
cin >> op + 1;
n = strlen(op + 1);
solve();
return 0;
}
UPD：如果需要在一个程序中多次使用该算法，需要清空tp数组。
height数组
height数组是应用后缀数组的利器。首先定义最长公共前缀lcp(i,j)：位置为i和位置为j的后缀的最长公共前缀长度。于是有height数组：
也就是说，height[i]表示排名为i和排名为i-1的后缀的最长公共前缀长度。规定height[1]=0。
如何求height数组？这需要利用一个重要性质（证明略）：
以此递推，不难写出代码：1
2
3
4
5
6
7
8
9
10
11
12inline void getHeight() {
int k = 0, j;
for (int i = 1; i <= n; i++) {
if (rk[i] == 1)h[rk[i]] = k = 0;
else {
if (k)k--;
j = sa[rk[i] - 1];
while (j + k <= n && i + k <= n && op[j + k] == op[i + k])++k;
h[rk[i]] = k;
}
}
}
后缀数组的应用
对后缀进行字典序排序实质上是利用了排序后相邻后缀差异尽可能小的性质，利用这个性质可以解决很多问题。
两个后缀的最大公共前缀
对于位置为i、j的两个后缀，其最大公共前缀长度为：
可以用ST表去维护。
可重叠最长重复子串
如果子串p在主串s中出现多次，则称p为重复子串，如果两个p可以有所重叠，在此基础上可以得到最长重复子串。该长度就是height数组的最大值。
不可重叠最长重复子串
考虑二分答案。对于答案k，可以将排序后的后缀分成若干组，其中每一组相邻的后缀间height都不小于k。这里的后缀分组必定是连续的分组。
容易知道可以使答案可行的后缀必存在与同一组中，但还要满足不重叠的性质。此时遍历每一个组，找到该组中最大的sa值和最小的sa值，如果存在一组最大值最小值的差不小于k，则k可行，否则不可行。时间复杂度$O(nlogn)$。
本质不相同的子串数量
一个字符串有很多子串，求它们其中本质不同的子串数目可以用后缀数组轻松解决。
一个子串必然是某个后缀的前缀，因此问题等价于所有后缀的本质不同的前缀数量。按字典序从小到大遍历所有后缀，这个后缀对答案的贡献为$len-sa[i]+1-height[i]$。这里$len-sa[i]+1$是这个后缀的所有前缀数目，减去height是减去重复的公共前缀数量。
例题
现在来通过一些例题来加深对后缀数组的认识。以下题目不涉及题面，可点开标题自查。
Musical Theme
楼教主男人八题之一。
题意是给一个字符串，找其中长度至少为5，不重叠的最长相似子串。这里的相似是指两个串长度相同且对应各位的差相同。
考虑差分。在原串中，我们求每一位与前一位的差，存入一个新串，易知新串中相同的两个串就对应原串中相似的串。那么问题转化成求新串中不可重叠最长重复子串的长度。
与朴素的不可重叠最长重复子串不同的是，本题还需要这两个串相差至少一个单位的距离，为什么这样请读者自行思考。但是由于本题数据过水，即使用最朴素的做法也是可以AC的。hack数据：9 1 1 1 1 1 1 1 1 1，答案为0，错误答案5。
注意特判n=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
using namespace std;
int n, sa[N], tp[N], rk[N], tax[N], M, h[N];
int op[N], op2[N];
inline void mySort() {
for (int i = 0; i <= M; i++)tax[i] = 0;
for (int i = 1; i <= n; i++)tax[rk[i]]++;
for (int i = 1; i <= M; i++)tax[i] += tax[i - 1];
for (int i = n; i >= 1; i--)sa[tax[rk[tp[i]]]--] = tp[i];
}
inline void solve() {
M = 180;
for (int i = 1; i <= n; i++)rk[i] = op[i] + 88, tp[i] = i;
mySort();
for (int w = 1, p = 0; p < n; M = p, w <<= 1) {
p = 0;
for (int i = 1; i <= w; i++)tp[++p] = n - w + i;
for (int i = 1; i <= n; i++)if (sa[i] > w)tp[++p] = sa[i] - w;
mySort();
for (int i = 1; i <= n; i++)tp[i] = rk[i];
rk[sa[1]] = p = 1;
for (int i = 2; i <= n; i++) {
rk[sa[i]] = (tp[sa[i - 1]] == tp[sa[i]] && tp[sa[i - 1] + w] == tp[sa[i] + w]) ? p : ++p;
}
}
}
inline void getHeight() {
int k = 0, j;
for (int i = 1; i <= n; i++) {
if (rk[i] == 1)h[rk[i]] = k = 0;
else {
if (k)k--;
j = sa[rk[i] - 1];
while (j + k <= n && i + k <= n && op[j + k] == op[i + k])++k;
h[rk[i]] = k;
}
}
}
inline bool check(int x) {
int minn = 0x3f3f3f3f, maxn = -0x3f3f3f3f;
for (int i = 2; i <= n; i++) {
if (h[i] < x) {
if (minn == 0x3f3f3f3f || maxn == -0x3f3f3f3f);
else if (maxn - minn > x)return true;//这里不是>=!!
minn = sa[i], maxn = sa[i];
} else minn = min(minn, sa[i]), maxn = max(maxn, sa[i]);
}
return minn != 0x3f3f3f3f && maxn != -0x3f3f3f3f && maxn - minn > x;//还有这里不是>=!!
}
int main() {
while (scanf("%d", &n)) {
if (n == 0)return 0;
for (int i = 1; i <= n; i++)scanf("%d", op2 + i);
for (int i = 1; i < n; i++)op[i] = op2[i + 1] - op2[i];//求差分
if (n == 1) {//特判1
printf("0\n");
continue;
}
--n, solve(), getHeight();//求后缀数组以及height数组
int l = 1, r = n + 1, mid;//二分答案
while (l < r) {//[,)
if (r == l + 1) {
if (l + 1 >= 5)printf("%d\n", l + 1);
else printf("0\n");
break;
}
mid = (l + r) >> 1;
if (check(mid))l = mid;
else r = mid;
}
}
return 0;
}
Milk Patterns
本质上是找最长k可重叠子串。
二分一个答案，然后将height分组，若某一个组中有不少于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
using namespace std;
int n, sa[N], tp[N], rk[N], tax[N], M, h[N], op[N], k, op2[N], m;
inline void mySort() {
for (int i = 0; i <= M; i++)tax[i] = 0;
for (int i = 1; i <= n; i++)tax[rk[i]]++;
for (int i = 1; i <= M; i++)tax[i] += tax[i - 1];
for (int i = n; i >= 1; i--)sa[tax[rk[tp[i]]]--] = tp[i];
}
inline void solve() {
M = 20005;
for (int i = 1; i <= n; i++)rk[i] = op[i], tp[i] = i;
mySort();
for (int w = 1, p = 0; p < n; M = p, w <<= 1) {
p = 0;
for (int i = 1; i <= w; i++)tp[++p] = n - w + i;
for (int i = 1; i <= n; i++)if (sa[i] > w)tp[++p] = sa[i] - w;
mySort();
for (int i = 1; i <= n; i++)tp[i] = rk[i];
rk[sa[1]] = p = 1;
for (int i = 2; i <= n; i++) {
rk[sa[i]] = (tp[sa[i - 1]] == tp[sa[i]] && tp[sa[i - 1] + w] == tp[sa[i] + w]) ? p : ++p;
}
}
}
inline void getHeight() {
int k = 0, j;
for (int i = 1; i <= n; i++) {
if (rk[i] == 1)h[rk[i]] = k = 0;
else {
if (k)k--;
j = sa[rk[i] - 1];
while (j + k <= n && i + k <= n && op[j + k] == op[i + k])++k;
h[rk[i]] = k;
}
}
}
inline bool check(int x) {
int num = 0;
for (int i = 2; i <= n; i++) {
if (h[i] < x) {
if (num >= k)return true;//不少于k个，答案可行
num = 0;
} else if (num == 0)num = 2;//这一个和上一个
else ++num;//加上当前的一个
}
return num >= k;
}
int main() {
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; i++)scanf("%d", op2 + i), op[i] = op2[i];
sort(op2 + 1, op2 + n + 1), m = unique(op2 + 1, op2 + n + 1) - op2 - 1;//离散化
for (int i = 1; i <= n; i++)op[i] = lower_bound(op2 + 1, op2 + m + 1, op[i]) - op2;
solve(), getHeight();
int l = 1, r = n + 1, mid;
while (l < r) {
if (r == l + 1) {
printf("%d", l);
return 0;
}
mid = (l + r) >> 1;
if (check(mid))l = mid;
else r = mid;
}
return 0;
}
New Distinct Substrings
就是求本质不同的子串数量，在上文应用中已经提及做法。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
using namespace std;
int n, sa[N], tp[N], rk[N], tax[N], M, h[N];
char op[N];
inline void mySort() {
for (int i = 0; i <= M; i++)tax[i] = 0;
for (int i = 1; i <= n; i++)tax[rk[i]]++;
for (int i = 1; i <= M; i++)tax[i] += tax[i - 1];
for (int i = n; i >= 1; i--)sa[tax[rk[tp[i]]]--] = tp[i];
}
inline void solve() {
M = 200;
for (int i = 1; i <= n; i++)rk[i] = op[i], tp[i] = i;
mySort();
for (int w = 1, p = 0; p < n; M = p, w <<= 1) {
p = 0;
for (int i = 1; i <= w; i++)tp[++p] = n - w + i;
for (int i = 1; i <= n; i++)if (sa[i] > w)tp[++p] = sa[i] - w;
mySort();
for (int i = 1; i <= n; i++)tp[i] = rk[i];
rk[sa[1]] = p = 1;
for (int i = 2; i <= n; i++) {
rk[sa[i]] = (tp[sa[i - 1]] == tp[sa[i]] && tp[sa[i - 1] + w] == tp[sa[i] + w]) ? p : ++p;
}
}
}
inline void getHeight() {
int k = 0, j;
for (int i = 1; i <= n; i++) {
if (rk[i] == 1)h[rk[i]] = k = 0;
else {
if (k)k--;
j = sa[rk[i] - 1];
while (j + k <= n && i + k <= n && op[j + k] == op[i + k])++k;
h[rk[i]] = k;
}
}
}
int main() {
int t;
scanf("%d", &t);
while (t--) {
scanf("%s", op + 1);
n = strlen(op + 1);
solve();
getHeight();
int ans = 0;
for (int i = 1; i <= n; i++)ans += n - sa[i] + 1 - h[i];
printf("%d\n", ans);
}
return 0;
}
Palindrome
找最长的回文子串串，并输出第一个。
其实可以用Manacher算法直接水过去，这里提一下后缀数组做法。
我们将原串的翻转串接到串的后面，中间加一个特殊字符相隔。问题转化求两个后缀的lcp，而求两个后缀的lcp可以用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
using namespace std;
int n, sa[N], tp[N], rk[N], tax[N], M, h[N], ST[N][20], bin[20], lg[N];
char op[N];
inline void mySort() {
for (int i = 0; i <= M; i++)tax[i] = 0;
for (int i = 1; i <= n; i++)tax[rk[i]]++;
for (int i = 1; i <= M; i++)tax[i] += tax[i - 1];
for (int i = n; i >= 1; i--)sa[tax[rk[tp[i]]]--] = tp[i];
}
inline void solve() {
M = 200;
for (int i = 1; i <= n; i++)rk[i] = op[i], tp[i] = i;
mySort();
for (int w = 1, p = 0; p < n; M = p, w <<= 1) {
p = 0;
for (int i = 1; i <= w; i++)tp[++p] = n - w + i;
for (int i = 1; i <= n; i++)if (sa[i] > w)tp[++p] = sa[i] - w;
mySort();
for (int i = 1; i <= n; i++)tp[i] = rk[i];
rk[sa[1]] = p = 1;
for (int i = 2; i <= n; i++) {
rk[sa[i]] = (tp[sa[i - 1]] == tp[sa[i]] && tp[sa[i - 1] + w] == tp[sa[i] + w]) ? p : ++p;
}
}
}
inline void getHeight() {
int k = 0, j;
for (int i = 1; i <= n; i++) {
if (rk[i] == 1)h[rk[i]] = k = 0;
else {
if (k)k--;
j = sa[rk[i] - 1];
while (j + k <= n && i + k <= n && op[j + k] == op[i + k])++k;
h[rk[i]] = k;
}
}
}
inline int getMin(int l, int r) {
if (rk[l] > rk[r])swap(l, r);
l = rk[l] + 1, r = rk[r];
int t = lg[r - l + 1];
return min(ST[l][t], ST[r - bin[t] + 1][t]);
}
int main() {
scanf("%s", op + 1);
n = strlen(op + 1), op[n + 1] = '$';
for (int i = 1; i <= n; i++)op[n + 1 + i] = op[n - i + 1];//拼接字符串
n = n << 1 | 1, solve(), getHeight();
for (int i = 1; i <= n; i++)ST[i][0] = h[i];//建立ST表
lg[0] = -1, bin[0] = 1;
for (int i = 1; i <= n; i++)lg[i] = lg[i >> 1] + 1;
for (int i = 1; i < 20; i++)bin[i] = bin[i - 1] << 1;
for (int i = 1; i < 20; i++) {
for (int j = 1; j <= n; j++) {
if (j + bin[i] - 1 <= n)ST[j][i] = min(ST[j][i - 1], ST[j + bin[i - 1]][i - 1]);
}
}
int ans = 0, pos = 0;
for (int i = 1; i <= (n - 1) >> 1; i++) {
int s = max((getMin(i, n + 1 - i) << 1) - 1, getMin(i, n + 2 - i) << 1);//前者是奇数情况，后者偶数
if (s > ans)ans = s, pos = i;
}
if (ans % 2)for (int i = pos - ((ans + 1) >> 1) + 1; i < (pos + ((ans + 1) >> 1)); i++)printf("%c", op[i]);
else for (int i = pos - (ans >> 1); i < (pos + (ans >> 1)); i++)printf("%c", op[i]);
return 0;
}
Power Strings
这个用SA也是能做的，但是用倍增会T，应该用DC3算法（然而我不会），于是这里就先说说kmp做法。
对串求next数组，然后可以发现最后一个next就是整个串的最长相同前后缀长度，如果$n-next[n]$能够将$n$整除，那么答案就是$\frac {n} {n-next[x]}$，否则为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
using namespace std;
char str[1000005];
int nxt[1000005], n;
void findNext() {
nxt[0] = nxt[1] = 0;
int j = 0, i = 2;
while (i <= n) {
if (str[j] == str[i - 1])nxt[i++] = ++j;
else if (j == 0)nxt[i++] = 0, j = 0;
else j = nxt[j];
}
}
int main() {
while (scanf("%s", str)) {
if (str[0] == '.')return 0;
n = strlen(str), findNext();
if (n % (n - nxt[n]) == 0)printf("%d\n", n / (n - nxt[n]));
else printf("1\n");
}
}
Maximum repetition substring
求重复指数最大的子串，并输出字典序最小的一个。重复指数的意义和上题相同。
枚举重复的子串长度，这里只考虑出现两次及以上的情况。易知如果一个子串是有长度为$l$的串重复拼接得到的，那么它必定包含字符$str[1]、str[1+l]、str[1+2l]…$这些字符中相邻的两个，并且它们是相同的。求出$height$并用$RMQ$找出$lcp(i,i+l)$，重复次数就是$lcp(i,i+l)/l+1$。
但是这样会使答案偏小，这是因为在$i$之前这个串的重复可能就已经开始了。考虑求$lcp(i,i+l)\%l$，若这个值为0，则易知向前挪一段位置也不会使答案增加，故这种情况不用考虑。当其不为0时，向前挪动$i$，使其到达$i-lcp(i,i+l)\%l$的位置，根据挪动后的$lcp(i,i+l)$来更新答案。
为什么不往前挪动更多距离？这样就是上一个$i$所做的了，对于当前的$i$，最多挪动$l-1$，否则没有意义。
这样，就可以在$O(nlogn)$的复杂度内找到最大的重复次数以及其子串长度。
最后，从$sa[1]$开始枚举，找到第一个符合条件的串，得到的一定是字典序最小的那一个。
注意特判$n=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
97
98
99
100
101
102
using namespace std;
int n, sa[N], tp[N], rk[N], tax[N], M, h[N], ST[N][20], bin[20], lg[N];
char op[N];
set<int> ssp;
inline void mySort() {
for (int i = 0; i <= M; i++)tax[i] = 0;
for (int i = 1; i <= n; i++)tax[rk[i]]++;
for (int i = 1; i <= M; i++)tax[i] += tax[i - 1];
for (int i = n; i >= 1; i--)sa[tax[rk[tp[i]]]--] = tp[i];
}
inline void solve() {
M = 200;
for (int i = 1; i <= n; i++)rk[i] = op[i], tp[i] = i;
mySort();
for (int w = 1, p = 0; p < n; M = p, w <<= 1) {
p = 0;
for (int i = 1; i <= w; i++)tp[++p] = n - w + i;
for (int i = 1; i <= n; i++)if (sa[i] > w)tp[++p] = sa[i] - w;
mySort();
for (int i = 1; i <= n; i++)tp[i] = rk[i];
rk[sa[1]] = p = 1;
for (int i = 2; i <= n; i++) {
rk[sa[i]] = (tp[sa[i - 1]] == tp[sa[i]] && tp[sa[i - 1] + w] == tp[sa[i] + w]) ? p : ++p;
}
}
}
inline void getHeight() {
int k = 0, j;
for (int i = 1; i <= n; i++) {
if (rk[i] == 1)h[rk[i]] = k = 0;
else {
if (k)k--;
j = sa[rk[i] - 1];
while (j + k <= n && i + k <= n && op[j + k] == op[i + k])++k;
h[rk[i]] = k;
}
}
}
inline int lcp(int l, int r) {
if (rk[l] > rk[r])swap(l, r);
l = rk[l] + 1, r = rk[r];
int t = lg[r - l + 1];
return min(ST[l][t], ST[r - bin[t] + 1][t]);
}
int main() {
int t = 1;
while (scanf("%s", op + 1)) {
if (op[1] == '#')return 0;
n = strlen(op + 1), solve(), getHeight(), lg[0] = -1, bin[0] = 1;
if (n == 1) {
printf("Case %d: %c\n", t++, op[1]);
continue;
}
for (int i = 1; i <= n; i++)lg[i] = lg[i >> 1] + 1;
for (int i = 1; i < 20; i++)bin[i] = bin[i - 1] << 1;
for (int i = 1; i <= n; i++)ST[i][0] = h[i];
for (int i = 1; i < 20; i++) {
for (int j = 1; j <= n; j++) {
if (j + bin[i] - 1 <= n)ST[j][i] = min(ST[j][i - 1], ST[j + bin[i - 1]][i - 1]);
}
}
int ans = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j + i <= n; j += i) {
int l = lcp(j, j + i), m = l / i + 1, q = l % i;
if (q != 0) {
q = j - q;//向前挪动
if (q >= 1)if (lcp(q, q + i) >= l)++m;//答案加一
}
if (m >= ans) {
if (m > ans)ssp.clear();
ssp.insert(i), ans = m;
}
}
}
for (int i = 1; i <= n; i++) {
for (set<int>::iterator it = ssp.begin(); it != ssp.end(); it++) {
int p = lcp(sa[i], sa[i] + *it);
if (p >= (ans - 1) * *it) {//可行判定
printf("Case %d: ", t++);
for (int j = sa[i]; j < sa[i] + ans * *it; j++)printf("%c", op[j]);
goto to;
}
}
}
to:
printf("\n");
}
return 0;
}
Long Long Message
题意就是求两个字符串的最长公共子串。
将第二个字符串拼接到第一个字符串的后面，中间用一个特殊字符分隔，然后二分答案，根据两个后缀位置分别在两个串内来判别答案正确性。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
using namespace std;
int n, sa[N], tp[N], rk[N], tax[N], M, h[N], len;
char op[N];
inline void mySort() {
for (int i = 0; i <= M; i++)tax[i] = 0;
for (int i = 1; i <= n; i++)tax[rk[i]]++;
for (int i = 1; i <= M; i++)tax[i] += tax[i - 1];
for (int i = n; i >= 1; i--)sa[tax[rk[tp[i]]]--] = tp[i];
}
inline void solve() {
M = 200;
for (int i = 1; i <= n; i++)rk[i] = op[i], tp[i] = i;
mySort();
for (int w = 1, p = 0; p < n; M = p, w <<= 1) {
p = 0;
for (int i = 1; i <= w; i++)tp[++p] = n - w + i;
for (int i = 1; i <= n; i++)if (sa[i] > w)tp[++p] = sa[i] - w;
mySort();
for (int i = 1; i <= n; i++)tp[i] = rk[i];
rk[sa[1]] = p = 1;
for (int i = 2; i <= n; i++) {
rk[sa[i]] = (tp[sa[i - 1]] == tp[sa[i]] && tp[sa[i - 1] + w] == tp[sa[i] + w]) ? p : ++p;
}
}
}
inline void getHeight() {
int k = 0, j;
for (int i = 1; i <= n; i++) {
if (rk[i] == 1)h[rk[i]] = k = 0;
else {
if (k)k--;
j = sa[rk[i] - 1];
while (j + k <= n && i + k <= n && op[j + k] == op[i + k])++k;
h[rk[i]] = k;
}
}
}
bool check(int x) {
int minn = 0x3f3f3f3f, maxn = -0x3f3f3f3f;
for (int i = 2; i <= n; i++) {
if (h[i] < x) {
if (minn == 0x3f3f3f3f);
else if (minn <= len && maxn > len + 1)return true;
minn = 0x3f3f3f3f, maxn = -0x3f3f3f3f;
} else if (minn == 0x3f3f3f3f)minn = min(sa[i - 1], sa[i]), maxn = max(sa[i - 1], sa[i]);
else minn = min(minn, sa[i]), maxn = max(maxn, sa[i]);
}
return minn <= len && maxn > len + 1;
}
int main() {
scanf("%s", op + 1), len = n = strlen(op + 1), op[n + 1] = '$', scanf("%s", op + n + 2);
n = strlen(op + 1), solve(), getHeight();
int l = 0, r = n + 1, mid;
while (l < r) {//[,)
if (r == l + 1) {
printf("%d", l);
return 0;
}
mid = (l + r) >> 1;
if (check(mid))l = mid;
else r = mid;
}
}
Common Substrings
这题真的不简单啊啊啊啊啊啊。题意是求两个字符串长度至少为k的重复子串数目。
首先将两个字符串拼起来，中间用一个特殊字符相连，然后求后缀数组以及height数组。下一步就可以枚举两个串的后缀，然后判其$lcp$，若$lcp\geq k$，则答案加上$lcp-k+1$。
这样枚举的复杂度是$O(n^2)$，不是什么好做法，一种优化思路是使用单调栈。
先弄清楚我们要做什么：枚举串$A$的所有后缀，然后枚举串$B$的所有后缀，求它们的$lcp$然后计入答案。这样的话，其实可以将此过程分为两个子过程。
从小到大枚举$height$数组的每一个值，若这个值对应的后缀来自串$A$，则计入其前面出现的所有$B$串的答案。然后再从小到大枚举$height$数组，对于来自串$B$的后缀，计入其前面出现过的所有串$A$的答案。容易知道经过这两次扫描，和枚举两个串的所有后缀效果是相同的。
（复杂度还是$O(n^2)$，有什么卵用）
这样的话，就可以利用单调性了。注意到两个后缀的$lcp$就是它们之间$height$的最小值。那么我们维护一个严格单调上升的栈，这里以第一个过程为例。
首先栈中只能存放$B$串的信息，其次它是单调的（根据height值）。我们用一个变量tot维护栈中所有$B$串后缀的贡献。当枚举到一个新的后缀时，我们需要适时弹栈。当该后缀的$height$不大于栈首对应$height$时，说明之前的$height$过大，$lcp$会因这个新加入的后缀缩小，故将所有不小于新后缀$height$的$B$串后缀弹出来，然后更新tot。不断重复这个过程就可以做到$O(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
86
87
88
89
90
91
92
93
94
using namespace std;
int n, sa[N], tp[N], rk[N], tax[N], M, h[N], len, k, sta[N][2], top;
//这里手写栈（sta）保存两个信息：sta[x][0]为height值，sta[x][1]为数量
char op[N];
long long ans, tot;
inline void mySort() {
for (int i = 0; i <= M; i++)tax[i] = 0;
for (int i = 1; i <= n; i++)tax[rk[i]]++;
for (int i = 1; i <= M; i++)tax[i] += tax[i - 1];
for (int i = n; i >= 1; i--)sa[tax[rk[tp[i]]]--] = tp[i];
}
inline void solve() {
M = 200;
for (int i = 1; i <= n; i++)rk[i] = op[i], tp[i] = i;
mySort();
for (int w = 1, p = 0; p < n; M = p, w <<= 1) {
p = 0;
for (int i = 1; i <= w; i++)tp[++p] = n - w + i;
for (int i = 1; i <= n; i++)if (sa[i] > w)tp[++p] = sa[i] - w;
mySort();
for (int i = 1; i <= n; i++)tp[i] = rk[i];
rk[sa[1]] = p = 1;
for (int i = 2; i <= n; i++) {
rk[sa[i]] = (tp[sa[i - 1]] == tp[sa[i]] && tp[sa[i - 1] + w] == tp[sa[i] + w]) ? p : ++p;
}
}
}
inline void getHeight() {
int k = 0, j;
for (int i = 1; i <= n; i++) {
if (rk[i] == 1)h[rk[i]] = k = 0;
else {
if (k)k--;
j = sa[rk[i] - 1];
while (j + k <= n && i + k <= n && op[j + k] == op[i + k])++k;
h[rk[i]] = k;
}
}
}
inline void add(int x) {
if (top == 0) {
if (sa[x] > len + 1)sta[++top][0] = inf, sta[top][1] = 1, tot = inf - k + 1;//新加入的元素都是无穷大的贡献，因为没有限制它的因素
return;
}
int ss = 0;
if (sa[x] > len + 1)tot += inf - k + 1;//先加上待加入元素的贡献
while (top && sta[top][0] >= h[x])tot -= sta[top][1] * (sta[top][0] - h[x]), ss += sta[top][1], top--;//弹栈，去除多余贡献
if (sa[x] <= len)ans += tot;//计入答案
if (ss)sta[++top][0] = h[x], sta[top][1] = ss;//被弹出的元素压缩
if (sa[x] > len + 1)sta[++top][0] = inf, sta[top][1] = 1;//弹入待入栈元素
}
inline void add2(int x) {//和add相似，只不过串A与串B反过来
if (top == 0) {
if (sa[x] <= len)sta[++top][0] = inf, sta[top][1] = 1, tot = inf - k + 1;
return;
}
int ss = 0;
if (sa[x] <= len)tot += inf - k + 1;
while (top && sta[top][0] >= h[x])tot -= sta[top][1] * (sta[top][0] - h[x]), ss += sta[top][1], top--;
if (sa[x] > len + 1)ans += tot;
if (ss)sta[++top][0] = h[x], sta[top][1] = ss;
if (sa[x] <= len)sta[++top][0] = inf, sta[top][1] = 1;
}
int main() {
while (scanf("%d", &k)) {
if (k == 0)return 0;
scanf("%s", op + 1), len = n = strlen(op + 1), op[n + 1] = '$', scanf("%s", op + n + 2);
n = strlen(op + 1), solve(), getHeight(), ans = tot = top = 0;
for (int i = 1; i <= n; i++) {//两次扫描
if (h[i] < k) tot = top = 0;
add(i);
}
tot = top = 0;
for (int i = 1; i <= n; i++) {
if (h[i] < k)tot = top = 0;
add2(i);
}
printf("%lld\n", ans);
}
}
Life Forms
求若干个字符串中，在多于一半的字符串中出现过的最长子串，并按照字典序输出。
仍然将这些字符串拼接起来，用特殊字符连接，但是这些特殊字符必须互不相同，然后求后缀数组以及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
using namespace std;
int n, sa[N], tp[N], rk[N], tax[N], M, h[N], len, k;
unsigned short int op[N], id[N];
set<int> ssp;
vector<int> vvp;
char op2[N];
inline void mySort() {
for (int i = 0; i <= M; i++)tax[i] = 0;
for (int i = 1; i <= n; i++)tax[rk[i]]++;
for (int i = 1; i <= M; i++)tax[i] += tax[i - 1];
for (int i = n; i >= 1; i--)sa[tax[rk[tp[i]]]--] = tp[i];
}
inline void solve() {
M = 300;
for (int i = 1; i <= n; i++)rk[i] = op[i], tp[i] = i;
mySort();
for (int w = 1, p = 0; p < n; M = p, w <<= 1) {
p = 0;
for (int i = 1; i <= w; i++)tp[++p] = n - w + i;
for (int i = 1; i <= n; i++)if (sa[i] > w)tp[++p] = sa[i] - w;
mySort();
for (int i = 1; i <= n; i++)tp[i] = rk[i];
rk[sa[1]] = p = 1;
for (int i = 2; i <= n; i++) {
rk[sa[i]] = (tp[sa[i - 1]] == tp[sa[i]] && tp[sa[i - 1] + w] == tp[sa[i] + w]) ? p : ++p;
}
}
}
inline void getHeight() {
int k = 0, j;
for (int i = 1; i <= n; i++) {
if (rk[i] == 1)h[rk[i]] = k = 0;
else {
if (k)k--;
j = sa[rk[i] - 1];
while (j + k <= n && i + k <= n && op[j + k] == op[i + k])++k;
h[rk[i]] = k;
}
}
}
inline bool check(int x) {
ssp.clear(), vvp.clear();
bool flag = false;
for (int i = 1; i <= n; i++) {
if (h[i] < x) {
if (ssp.size() >= ((k >> 1) + 1))vvp.push_back(sa[i - 1]), flag = true;
ssp.clear();
} else if (ssp.empty())ssp.insert(id[sa[i]]), ssp.insert(id[sa[i - 1]]);
else ssp.insert(id[sa[i]]);
}
return flag;
}
int main() {
int lock = 0;
// freopen("text.in", "r", stdin);
while (scanf("%d", &k)) {
if (lock)printf("\n");
else lock = 1;
if (k == 0)return 0;
memset(id, 0, sizeof(id)), memset(tp, 0, sizeof(tp));
for (int i = 1, now = 0; i <= k; i++) {
scanf("%s", op2 + 1), len = strlen(op2 + 1);
for (int j = 1; j <= len; j++)op[j + now] = op2[j], id[j + now] = i;
op[now + len + 1] = 200 + i, now += len + 1;
if (i == k)n = now - 1;
}
solve(), getHeight();
int l = 0, r = n + 1, mid;
while (l < r) {
if (r == l + 1) {
if (l == 0)printf("?\n");
else {
check(l);
for (int i = 0; i < vvp.size(); i++) {
for (int j = vvp[i]; j < vvp[i] + l; j++)printf("%c", op[j]);
printf("\n");
}
}
break;
}
mid = (l + r) >> 1;
if (check(mid))l = mid;
else r = mid;
}
}
}
Relevant Phrases of Annihilation
就是找在一堆字符串中都出现过至少两次并且不重叠的最长子串。
还是拼接字符串，然后二分答案，记录这一组中每一个后缀的来源，判定它们是否重叠即可。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
using namespace std;
int n, sa[N], tp[N], rk[N], tax[N], M, h[N], len, k;
int maxn[15], minn[15];
unsigned short int op[N], id[N];
char op2[N];
inline void mySort() {
for (int i = 0; i <= M; i++)tax[i] = 0;
for (int i = 1; i <= n; i++)tax[rk[i]]++;
for (int i = 1; i <= M; i++)tax[i] += tax[i - 1];
for (int i = n; i >= 1; i--)sa[tax[rk[tp[i]]]--] = tp[i];
}
inline void solve() {
M = 300;
for (int i = 1; i <= n; i++)rk[i] = op[i], tp[i] = i;
mySort();
for (int w = 1, p = 0; p < n; M = p, w <<= 1) {
p = 0;
for (int i = 1; i <= w; i++)tp[++p] = n - w + i;
for (int i = 1; i <= n; i++)if (sa[i] > w)tp[++p] = sa[i] - w;
mySort();
for (int i = 1; i <= n; i++)tp[i] = rk[i];
rk[sa[1]] = p = 1;
for (int i = 2; i <= n; i++) {
rk[sa[i]] = (tp[sa[i - 1]] == tp[sa[i]] && tp[sa[i - 1] + w] == tp[sa[i] + w]) ? p : ++p;
}
}
}
inline void getHeight() {
int k = 0, j;
for (int i = 1; i <= n; i++) {
if (rk[i] == 1)h[rk[i]] = k = 0;
else {
if (k)k--;
j = sa[rk[i] - 1];
while (j + k <= n && i + k <= n && op[j + k] == op[i + k])++k;
h[rk[i]] = k;
}
}
}
inline bool check(int x) {
int num = 0;
for (int i = 1; i <= k; i++)minn[i] = 0x3f3f3f3f, maxn[i] = -0x3f3f3f3f;
for (int i = 1; i <= n; i++) {
if (h[i] < x) {
bool lk = true;
for (int j = 1; j <= k; j++) {
if (minn[j] == 0x3f3f3f3f)lk = false;
else if (maxn[j] - minn[j] < x)lk = false;
}
if (lk)return true;
for (int j = 1; j <= k; j++)minn[j] = 0x3f3f3f3f, maxn[j] = -0x3f3f3f3f;
num = 0;
} else if (num == 0) {
minn[id[sa[i - 1]]] = min(minn[id[sa[i - 1]]], sa[i - 1]);
maxn[id[sa[i - 1]]] = max(maxn[id[sa[i - 1]]], sa[i - 1]);
minn[id[sa[i]]] = min(minn[id[sa[i]]], sa[i]);
maxn[id[sa[i]]] = max(maxn[id[sa[i]]], sa[i]);
num = 2;
} else minn[id[sa[i]]] = min(minn[id[sa[i]]], sa[i]), maxn[id[sa[i]]] = max(maxn[id[sa[i]]], sa[i]), ++num;
}
return false;
}
int main() {
int t;
scanf("%d", &t);
while (t--) {
scanf("%d", &k);
if (k == 0)return 0;
memset(id, 0, sizeof(id)), memset(tp, 0, sizeof(tp));
for (int i = 1, now = 0; i <= k; i++) {
scanf("%s", op2 + 1), len = strlen(op2 + 1);
for (int j = 1; j <= len; j++)op[j + now] = op2[j], id[j + now] = i;
op[now + len + 1] = 200 + i, now += len + 1;
if (i == k)n = now - 1;
}
solve(), getHeight();
int l = 0, r = n + 1, mid;
while (l < r) {
if (r == l + 1) {
printf("%d\n", l);
break;
}
mid = (l + r) >> 1;
if (check(mid))l = mid;
else r = mid;
}
}
return 0;
}
Alice’s Classified Message
查询后缀与后缀的最长公共前缀。
构造SA，然后求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
using namespace std;
int n, sa[N], tp[N], rk[N], tax[N], M, h[N], now;
char op[N];
inline void mySort() {
for (int i = 0; i <= M; i++)tax[i] = 0;
for (int i = 1; i <= n; i++)tax[rk[i]]++;
for (int i = 1; i <= M; i++)tax[i] += tax[i - 1];
for (int i = n; i >= 1; i--)sa[tax[rk[tp[i]]]--] = tp[i];
}
inline void solve() {
M = 30;
for (int i = 1; i <= n; i++)rk[i] = op[i] - 'a' + 1, tp[i] = i;
mySort();
for (int w = 1, p = 0; p < n; M = p, w <<= 1) {
p = 0;
for (int i = 1; i <= w; i++)tp[++p] = n - w + i;
for (int i = 1; i <= n; i++)if (sa[i] > w)tp[++p] = sa[i] - w;
mySort();
for (int i = 1; i <= n; i++)tp[i] = rk[i];
rk[sa[1]] = p = 1;
for (int i = 2; i <= n; i++) {
rk[sa[i]] = (tp[sa[i - 1]] == tp[sa[i]] && tp[sa[i - 1] + w] == tp[sa[i] + w]) ? p : ++p;
}
}
}
inline void getHeight() {
int k = 0, j;
for (int i = 1; i <= n; i++) {
if (rk[i] == 1)h[rk[i]] = k = 0;
else {
if (k)k--;
j = sa[rk[i] - 1];
while (j + k <= n && i + k <= n && op[j + k] == op[i + k])++k;
h[rk[i]] = k;
}
}
}
int main() {
int t = 1, T;
scanf("%d", &T);
while (T--) {
scanf("%s", op + 1), printf("Case #%d:\n-1 %d\n", t++, op[1]);
memset(tp, 0, sizeof(tp)), n = strlen(op + 1), solve(), getHeight(), now = 2;
while (now <= n) {
int k = 0, minn = 0x7fffffff, pos = 0x7fffffff;
for (int i = rk[now] - 1; i >= 1; i--) {
minn = min(minn, h[i + 1]);
if (minn < k)break;
if (sa[i] < now)pos = min(pos, sa[i]), k = minn;
}
minn = 0x7fffffff;
for (int i = rk[now] + 1; i <= n; i++) {
minn = min(minn, h[i]);
if (minn < k)break;
if (sa[i] < now) {
if (minn > k)k = minn, pos = sa[i];
else pos = min(pos, sa[i]);
}
}
if (k == 0)printf("-1 %d\n", op[now++]);
else printf("%d %d\n", k, pos - 1), now += k;
}
}
return 0;
}
The Number of Palindromes
本质不同的回文串数量。
首先改造原串，一遍Manacher算出每一个字符的最长回文半径，然后用后缀数组去重。
去重的时候，我们从小到大遍历sa，记录上一个被计入的回文串长度，用height数组求出与其的lcp，根据lcp减去被重复计入的回文串。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
using namespace std;
char op[N], op2[N];
int n, sa[N], h[N], tp[N], rk[N], M, tax[N], p[N];
inline void mySort() {
for (int i = 0; i <= M; i++)tax[i] = 0;
for (int i = 1; i <= n; i++)tax[rk[i]]++;
for (int i = 1; i <= M; i++)tax[i] += tax[i - 1];
for (int i = n; i >= 1; i--)sa[tax[rk[tp[i]]]--] = tp[i];
}
inline void solve() {
M = 500;
for (int i = 1; i <= n; i++)rk[i] = op[i] - '#' + 1, tp[i] = i;
mySort();
for (int w = 1, p = 0; p < n; M = p, w <<= 1) {
p = 0;
for (int i = 1; i <= w; i++)tp[++p] = n - w + i;
for (int i = 1; i <= n; i++)if (sa[i] > w)tp[++p] = sa[i] - w;
mySort();
for (int i = 1; i <= n; i++)tp[i] = rk[i];
rk[sa[1]] = p = 1;
for (int i = 2; i <= n; i++) {
rk[sa[i]] = (tp[sa[i - 1]] == tp[sa[i]] && tp[sa[i - 1] + w] == tp[sa[i] + w]) ? p : ++p;
}
}
}
inline void getHeight() {
int k = 0, j;
for (int i = 1; i <= n; i++) {
if (rk[i] == 1)h[rk[i]] = k = 0;
else {
if (k)k--;
j = sa[rk[i] - 1];
while (j + k <= n && i + k <= n && op[j + k] == op[i + k])++k;
h[rk[i]] = k;
}
}
}
int main() {
int t = 1, T, l;
scanf("%d", &T);
while (T--) {
scanf("%s", op2 + 1), n = strlen(op2 + 1), memset(tp, 0, sizeof(tp));
for (int i = 1, j = 1, k = 0; i <= n; k ^= 1) {
if (!k)op[j++] = '#';
else op[j++] = op2[i++];
l = j;
}
int pos = 0, r = 1, ans = 0, tmp = 0;
op[n = l] = '#', p[0] = 1, solve(), getHeight();
for (int i = 1; i <= n; i++)op2[i - 1] = op[i];
for (int i = 1; i < n; i++) {
if (i < r)p[i] = min(p[2 * pos - i], r - i);
else p[i] = 1;
for (; i - p[i] >= 0 && i + p[i] <n && op2[i - p[i]] == op2[i + p[i]]; ++p[i]);
if (p[i] + i > r)r = p[i] + i, pos = i;
}
for (int i = n; i >= 1; i--)p[i] = p[i - 1];
for (int i = 1; i <= n; i++) {
int x = sa[i];
tmp = min(tmp, h[i]);//tmp是上一次计入的长度，与lcs取较小值
if (p[x] <= tmp)continue;//回文串本身就短，一定全部都算过了，不再计入
ans += (p[x] - tmp) / 2;//由于加入了#字符，故需要除以2
tmp = p[x];
}
printf("Case #%d: %d\n", t++, ans);
}
return 0;
}
Boring String Problem
找第k小的子串，不重复计入重数。
处理出每一个后缀特有的子串数量，易知这些子串就是按照字典序排列的，只需要二分出第k小的那一个即可。
由于需要左端点最小，因此还需要向后枚举找到最小的左端点，这里需要根据lcp来判断。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
using namespace std;
int n, sa[N], tp[N], rk[N], tax[N], M, h[N];
long long f[N];
char op[N];
inline void mySort() {
for (int i = 0; i <= M; i++)tax[i] = 0;
for (int i = 1; i <= n; i++)tax[rk[i]]++;
for (int i = 1; i <= M; i++)tax[i] += tax[i - 1];
for (int i = n; i >= 1; i--)sa[tax[rk[tp[i]]]--] = tp[i];
}
inline void solve() {
M = 30;
for (int i = 1; i <= n; i++)rk[i] = op[i] - 'a' + 1, tp[i] = i;
mySort();
for (int w = 1, p = 0; p < n; M = p, w <<= 1) {
p = 0;
for (int i = 1; i <= w; i++)tp[++p] = n - w + i;
for (int i = 1; i <= n; i++)if (sa[i] > w)tp[++p] = sa[i] - w;
mySort();
for (int i = 1; i <= n; i++)tp[i] = rk[i];
rk[sa[1]] = p = 1;
for (int i = 2; i <= n; i++) {
rk[sa[i]] = (tp[sa[i - 1]] == tp[sa[i]] && tp[sa[i - 1] + w] == tp[sa[i] + w]) ? p : ++p;
}
}
}
inline void getHeight() {
int k = 0, j;
for (int i = 1; i <= n; i++) {
if (rk[i] == 1)h[rk[i]] = k = 0;
else {
if (k)k--;
j = sa[rk[i] - 1];
while (j + k <= n && i + k <= n && op[j + k] == op[i + k])++k;
h[rk[i]] = k;
}
}
}
int main() {
// freopen("text.in", "r", stdin);
while (scanf("%s", op + 1) != EOF) {
memset(tp, 0, sizeof(tp)), n = strlen(op + 1), solve(), getHeight();
for (int i = 1; i <= n; i++)f[i] = n - sa[i] + 1 - h[i];
for (int i = 1; i <= n; i++)f[i] += f[i - 1];
long long q, l = 0, r = 0, L, R, mid, k, len;
scanf("%lld", &q);
while (q--) {
scanf("%lld", &k), k = (l ^ r ^ k) + 1;
if (k > f[n]) {
printf("%lld %lld\n", l = 0, r = 0);
continue;
}
L = 1, R = n;
while (L <= R) {
if (L == R)break;
mid = (L + R) >> 1;
if (f[mid] < k)L = mid + 1;
else R = mid;
}
l = sa[L], r = sa[L] + h[L] + k - f[L - 1] - 1, len = r - l + 1;
for (int i = L + 1; i <= n; i++) {
if (h[i] >= len) {
if (sa[i] < l)l = sa[i], r = l + len - 1;
} else break;
}
printf("%lld %lld\n", l, r);
}
}
return 0;
}
[SCOI2012]喵星球上的点名
好题啊，这个问题可以用很多种方法去解决。
首先将所有名和姓以及点名串连起来，中间用特殊字符连接，然后构造SA以及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
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
using namespace std;
int n, sa[N], tp[N], rk[N], tax[N], m, M, h[N], ST[N][25], bin[25], lg[N], ID = 10000, ct;
int fid[N], to[200005], op[N], L[200005], be[N], num[200005], sum[200005], nn, id[N];
struct Q {
int l, r, rk, ans;
bool operator<(Q q) {
if (be[l] != be[q.l])return be[l] < be[q.l];
return be[r] < be[q.r];
}
} q[200005];
inline void mySort() {
for (int i = 0; i <= M; i++)tax[i] = 0;
for (int i = 1; i <= n; i++)tax[rk[i]]++;
for (int i = 1; i <= M; i++)tax[i] += tax[i - 1];
for (int i = n; i >= 1; i--)sa[tax[rk[tp[i]]]--] = tp[i];
}
inline void solve() {
M = 500005;
for (int i = 1; i <= n; i++)rk[i] = op[i], tp[i] = i;
mySort();
for (int w = 1, p = 0; p < n; M = p, w <<= 1) {
p = 0;
for (int i = 1; i <= w; i++)tp[++p] = n - w + i;
for (int i = 1; i <= n; i++)if (sa[i] > w)tp[++p] = sa[i] - w;
mySort();
for (int i = 1; i <= n; i++)tp[i] = rk[i];
rk[sa[1]] = p = 1;
for (int i = 2; i <= n; i++) {
rk[sa[i]] = (tp[sa[i - 1]] == tp[sa[i]] && tp[sa[i - 1] + w] == tp[sa[i] + w]) ? p : ++p;
}
}
}
inline void getHeight() {
int k = 0, j;
for (int i = 1; i <= n; i++) {
if (rk[i] == 1)h[rk[i]] = k = 0;
else {
if (k)k--;
j = sa[rk[i] - 1];
while (j + k <= n && i + k <= n && op[j + k] == op[i + k])++k;
h[rk[i]] = k;
}
}
}
inline int lcp(int l, int r) {
++l;
int t = lg[r - l + 1];
return min(ST[l][t], ST[r - bin[t] + 1][t]);
}
bool cmp(Q a, Q b) {
return a.rk < b.rk;
}
int main() {
scanf("%d%d", &nn, &m);
for (int i = 1, l; i <= nn; i++) {
scanf("%d", &l);
for (int j = 1; j <= l; j++)++ct, scanf("%d", op + ct), fid[ct] = i;
op[++ct] = ++ID;
scanf("%d", &l);
for (int j = 1; j <= l; j++)++ct, scanf("%d", op + ct), fid[ct] = i;
op[++ct] = ++ID;
}
for (int i = 1, l; i <= m; i++) {
scanf("%d", &l), to[i] = ct + 1, L[i] = l;
for (int j = 1; j <= l; j++)++ct, scanf("%d", op + ct);
op[++ct] = ++ID;
}
n = ct, solve(), getHeight(), lg[0] = -1, bin[0] = 1;
for (int i = 1; i <= n; i++)lg[i] = lg[i >> 1] + 1;
for (int i = 1; i < 25; i++)bin[i] = bin[i - 1] << 1;
for (int i = 1; i <= n; i++)ST[i][0] = h[i];
for (int i = 1; i < 25; i++) {
for (int j = 1; j <= n; j++) {
if (j + bin[i] - 1 <= n)ST[j][i] = min(ST[j][i - 1], ST[j + bin[i - 1]][i - 1]);
}
}
for (int i = 1; i <= m; i++) {
int p = rk[to[i]], l = 0, r = p - 1, mid;
while (l < r) {//(,]
if (r == l + 1) {
if (lcp(r, p) == L[i])q[i].l = r;
else q[i].l = p;
break;
}
mid = (l + r) >> 1;
if (lcp(mid, p) >= L[i])r = mid;
else l = mid;
}
l = p + 1, r = n + 1, q[i].rk = i;
while (l < r) {//[,)
if (r == l + 1) {
if (lcp(p, l) == L[i])q[i].r = l;
else q[i].r = p;
break;
}
mid = (l + r) >> 1;
if (lcp(p, mid) >= L[i])l = mid;
else r = mid;
}
}
for (int i = 1; i <= n; i++)id[i] = fid[sa[i]];
int base = sqrt(n), l = 1, r = 1, ans = 0;
for (int i = 1; i <= n; i++)be[i] = (i - 1) / base + 1;
sort(q + 1, q + m + 1);
if (id[1] != 0)++num[id[1]], ++ans, sum[id[1]] += m;
for (int i = 1; i <= m; i++) {
while (l < q[i].l) {
--num[id[l]];
if (id[l] != 0 && num[id[l]] == 0)--ans, sum[id[l]] -= m - i + 1;
++l;
}
while (l > q[i].l) {
++num[id[l - 1]];
if (id[l - 1] != 0 && num[id[l - 1]] == 1)++ans, sum[id[l - 1]] += m - i + 1;
--l;
}
while (r < q[i].r) {
++num[id[r + 1]];
if (id[r + 1] != 0 && num[id[r + 1]] == 1)++ans, sum[id[r + 1]] += m - i + 1;
++r;
}
while (r > q[i].r) {
--num[id[r]];
if (id[r] != 0 && num[id[r]] == 0)--ans, sum[id[r]] -= m - i + 1;
--r;
}
q[i].ans = ans;
}
sort(q + 1, q + m + 1, cmp);
for (int i = 1; i <= m; i++)printf("%d\n", q[i].ans);
for (int i = 1; i <= nn; i++)printf("%d ", sum[i]);
return 0;
}
[NOI2016]优秀的拆分
如果我们能求两个数组$suf[x]$和$pre[x]$分别表示以$x$开始的AA串数量，以$x$结尾的AA串数量，那么答案就是：
现在就要求这两个数组。首先可以ST+SA然后$O(n^2)$去求，但这样显然不是什么好做法。
上面的问题（具体来说，是Maximum repetition substring这个题）中，曾用到一个巧妙的做法：枚举长度然后打关键点。这种做法基于一个事实：一个某种长度的AA串，必然会经过两个相邻的关键点。严格地说，是对于长度为$2l$的AA串，必然会唯一地经过一个相邻的关键点对。这样我们对于一个长度，遍历所有关键点，就可以找到所有AA串。
假设现在长度为$l$，关键点是$x$和$x+l$，考虑如何找对应的AA串。
首先找$x$和$x+l$的$lcp$以及$x-1$和$x+l-1$的$lcs$，易知如果它们的和不到$l$，即$lcs+lcp<l$，那么必然不会有一个长为$2l$的AA串经过这两个点。否则一定会有。
最普通的情况是$lcp+lcs=l$，这样对应一个唯一的串。事实上，在求出$lcs$和$lcp$后，这会对应$lcs+lcp-l+1$个长度为$2l$的AA串。但是这些AA串不一定都经过这两个点，需要进行裁剪，裁剪后，我们就可以得到一些区间，然后我们根据这些区间更新$suf$和$pre$数组，就可以得到这两个数组。这里的更新可以用差分实现。
1 | #include <iostream> |