Dyd's Blog

He who has a strong enough why can bear almost any how.

后缀数组

Posted on Edited on In
Symbols count in article: 16k Reading time ≈ 15 mins.

字符串总是让人头疼

后缀数组

前置知识：基数排序

首先保证值域为 $[0, n] \wedge \mathbb{Z}$

然后统计每个数有多少个，记作 $cnt[i]$ ，然后将 $cnt$ 求出前缀和，此时 $cnt[i]$ 就是“小于等于 $i$ 的数的个数”，倒序扫描每一个数（倒序是为了使排序稳定），扫到 $i$ 就令 $i$ 的排名为 $cnt[i]$ ，并 $–cnt[i]$ ，由此就可以做到单关键字基数排序，时间为 $O(n)$

对于双关键字，我们先对第二关键字进行排序，然后不管第二关键字，只对第一关键字进行基数排序，由于基数排序是稳定的，所以当第一关键字相同时，第二关键字仍然是有序的

定义

后缀数组是一种针对字符串的数据结构，为了方便，我们统一令字符串的下标从1开始

  • 字符串：由字符组成的序列，用大写字母表示，如 $T = ababbcbac$ ，记其长度为 $len(T)$
  • 子串：一个字符串的某一段，记作 $T[2, 5] = babb$ ，其中 $[2, 5]$ 是下标区间
  • 后缀：一个长度为 $len$ 的字符串有 $len$ 个后缀子串，为 $\{S \mid S = T[i, len], i \in [1, n]\}$ ，为了方便，称从 $i$ 开头的后缀为“第 $i$ 个后缀”，记作 $suf(i)$ （suffix），即 $suf(i) = T[i, len]$
  • 前缀：我们将串 $T$ 长度为 $len$ 的前缀 $T[1, len]$ 记为 $T^{len}$
  • 后缀数组 $SA[i]$ ：排名第 $i$ 的后缀是 $suf(SA[i])$ ，注意区别“排名为 $i$ ”和“第 $i$ 个后缀”
  • 排名数组 $rk[i]$ ：第 $i$ 个后缀的排名是 $rk[i]$
  • $hei[i]$ （height）： $suf(SA[i])$ 与 $suf(SA[i - 1])$ 的LCP（最长公共前缀），可指字符串，也可指长度
  • $lcp(i, j)$ ： $suf(SA[i])$ 和 $suf(SA[j])$ 的LCP
  • $h(i)$ ：第 $i$ 个后缀与排名在其前面的第一个后缀的LCP，即 $h(i) = hei[rk[i]]$

求法

SA/rk

求后缀数组 $SA$ 一般用倍增算法求出（同时 $rk$ 也就求出来了），时间复杂度为 $O(n \log n)$

首先我们想如何对 $\{suf(i)\}$ 排序，由整数排序的方法我们知道，至少要进行 $n \log n$ 次比较，但是，字符串比较的时间复杂度为 $O(n)$ ，故直接比较时间为 $O(n^2 \log n)$

不难想到，如果能让字符串对应上数字（且大小关系对应）不就可以直接比较了吗？倍增算法就基于此，其流程如下：

  1. 假设我们要比较 $\{S_i[l, r]\}$ ，取 $mid = \frac{l + r}{2}$ ，递归比较 $\{S_i[l, mid]\}$ 和 $\{S_i[mid + 1, r]\}$ ；递归的边界是当 $S_i[l, r]$ 只有一个字符，可以直接排序
  2. 假设递归完毕，则 $\{S_i[l, mid]\}$ 和 $\{S_i[mid + 1, r]\}$ 已经有序，扫一遍可以把他们离散化到整数，设 $S_i[p, q] \rightarrow A_i[p, q]$ ，现在 $S_i[l, r]$ 被变成了整数二元组 $(A_i[l, mid], A_i[mid + 1, r])$ ，直接排序即可

以上会递归 $\log n$ 层，每次基数排序为 $O(n)$ ，总时间复杂度为 $O(n \log n)$ 具体实现时常用循环代替递归

ps：其实有 $O(n)$ 的DC3算法，但不常用（常数大+难打），有时间再写吧（挖坑）

hei

首先证明三个引理：

引理1：
$$
lcp(i, j) = \min(lcp(i, k), lcp(k, j)),i \le k \le j
$$
即对于任意的 $i \le k \le j$ ，排名第 $i$ 的后缀和排名第 $j$ 的后缀的LCP就是排名第 $k$ 的后缀和它们分别的LCP中较小值

引理1

证明：

排名为 $i$ 的后缀为 $S_i$ ，设 $T = \min(lcp(i, k), lcp(k, j)), R = lcp(i, j)$

首先若 $R < T$ ，那么由于 $lcp(i, k) \ge T$ ，所以 $i$ 的一定有前缀 $T$ ，而 $j$ 也有前缀 $T$ ，则 $lcp(i, j) = T$ ，矛盾，故 $lcp(i, j) \ge T$

然后若 $R > T$ ，那么因为 $S_i[1, R] = S_j[1, R]$ ，又z因为排名， $S_i[1, R] \le S_k[1, R] \le S_j[1, R]$ ，则 $S_i[1, R] = S_k[1, R] = S_j[1, R]$ ，则 $T = R$ ，矛盾

综上，$T = R$ 引理得证

引理2：
$$
lcp(i, j) = \min(lcp(i, i + 1), lcp(i + 1, i + 2), …, lcp(j - 1, j)), i \le j
$$
即对于任意的 $i \le j$ 排名第 $i$ 的后缀和排名第 $j$ 的后缀的LCP就是它们之间的后缀（包括它们）中相邻两个的LCP的最小值

证明：

由引理1，有 $\min(lcp(i, i + 1), lcp(i + 1, i + 2)) = lcp(i, i + 2)$ 不断以此类推，即得引理2

这个引理也可以表示为：
$$
lcp(i, j) = \min_{i < k \le j} \{ hei[k]\}
$$
用这个引理可以将后缀的LCP转化为RMQ，ST表可以做到 $O(1)$

引理3：
$$
h(i) \ge h(i - 1) - 1
$$
$h(i - 1) \le 1$ 时显然成立

当 $h(i - 1) > 1$ 时，不妨设 $k = SA[rk[i - 1] - 1]$ ，即排名在第 $i$ 个后缀（不是排名为 $i$ 的后缀）前面的第一个后缀是第 $k$ 个后缀，同理设 $r = SA[rk[i] - 1]$

有 $h(i - 1) = lcp(suf(i - 1), suf(k))$ ，将这两个字符串各自去掉第一个字符，因为它们的LCP大于1，所以这个字符一定相等，则有 $lcp(suf(k + 1), suf(i)) = h(i - 1) - 1$ 且 $suf(k + 1)$ 排在 $suf(i)$ 前面，则由引理1有
$$
\begin{aligned}
h(i - 1) - 1
&= lcp(suf(k + 1), suf(i))\\
&= \min(lcp(suf(k + 1), suf(r)), lcp(suf(r), suf(i)))\\
&\le lcp(suf(r), suf(i))\\
&= h(i)
\end{aligned}
$$
故 $h(i) \ge h(i - 1) - 1$

有了上面三个引理，我们来看如何求 $hei$

我们枚举 $1 \le i \le n$ ，计算 $hei[rk[i]]$

对于 $rk[i] = 1$ ，不必管，因为 $hei[1] = 0$ ，否则令 $k = h(i - 1) - 1$ （特别的，若 $h(i - 1) \le 1$ ，就让 $k = 0$ ），然后暴力求 $k$ 还能向后走多少，易知时间为 $O(n)$ （因为 $k$ 最多减 $n$ ，而最大为 $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
#include <bits/stdc++.h>
#define STC static
using namespace std;
const int N = 1e6 + 5;
int n;
char s[N];
int sa[N], rk[N], hei[N];
void get_sa(int _num)
{
	STC int x[N], y[N], c[N]; //排序用,第一关键字,第二关键字,cnt
	for (int i = 1; i <= n; ++i)
		++c[x[i] = s[i]]; //第一次只有一个字符,不必离散化
	for (int i = 2; i <= _num; ++i)
		c[i] += c[i - 1];
	for (int i = n; i >= 1; --i)
		sa[c[x[i]]--] = i;
	for (int k = 1, num; k <= n; k <<= 1) //k枚举关键字长度,合并后长度应为2k
	{
		num = 0; //记录离散化后的值域
		//先以第二关键字排序
		for (int i = n - k + 1; i <= n; ++i)  //没有第二关键字的牌最前
			y[++num] = i;
		for (int i = 1; i <= n; ++i)
			if (sa[i] > k)
				y[++num] = sa[i] - k;
		//以第一关键字排序
		for (int i = 1; i <= _num; ++i)
			c[i] = 0;
		for (int i = 1; i <= n; ++i)
			++c[x[i]];
		for (int i = 2; i <= _num; ++i)
			c[i] += c[i - 1];
		for (int i = n; i >= 1; --i)
			sa[c[x[y[i]]]--] = y[i], y[i] = 0;  //这里清空y实际上是清空x,因为后面交换了
		swap(x, y);
		//将排好序的字符串离散化
		x[sa[1]] = num = 1;
		for (int i = 2; i <= n; ++i)
			x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) ? num : ++num;
		if (num == n)
			break;
		_num = num;
	}
	for (int i = 1; i <= n; ++i)
		rk[sa[i]] = i;
}
void get_hei()
{
	int k = 0;
	for (int i = 1; i <= n; ++i)
	{
		if (rk[i] == 1)
			continue;
		if (k)
			--k;
		int j = sa[rk[i] - 1];
		while (i + k <= n && j + k <= n && s[i + k] == s[j + k])
			++k;
		hei[rk[i]] = k;
	}
}
int main()
{
	scanf("%s", s + 1);
	n = strlen(s + 1);
	get_sa('z');
	get_hei();
	for (int i = 1; i <= n; ++i)
		printf("%d ", sa[i]);
	putchar('\n');
	for (int i = 1; i <= n; ++i)
		printf("%d ", hei[i]);
	return 0;
}

应用

SA的应用主要是通过引理2来实现的

模式串匹配

考虑如下问题：给定模式串 $P$ 和长度为 $n$ 的文本串 $T$ 询问 $P$ 在 $T$ 中出现的情况

当 $P$ 只有一个时，就是kmp，当有多个 $P$ 时，也可以AC自动机，以上算法都是 $O(n)$ 的，那么后缀数组如何比较好的解决该问题

首先不难想到， $T$ 的任意一个子串都一定可以对应到唯一一个后缀的前缀，具体的， $T[l, r] \leftrightarrow suf(l)^r$

那么考虑构造出 $T$ 的后缀数组，由于 $T$ 的后缀已经被排好了序，可以二分查找每个后缀是否有前缀 $P$ ，具体的，若我们二分到了区间 $[l, r]$ ：

  1. 如果 $P$ 是 $suf(SA[mid])$ 的前缀，说明这就是 $P$ 在 $T$ 中的出现，所有 $lcp(mid, j) \ge len(P)$ 的 $j$ 也是 $P$ 的出现
  2. 如果 $P \le suf(SA(mid))$ ，进入区间 $[l, mid - 1]$ ，否则进入 $[mid + 1, r]$

以上算法的时间复杂度为 $O(len(P) \log n)$ ，时间主要消耗在第二步的比较上，可以用 $hei$ 数组优化

假设到当前为止，获得的最大前缀匹配长度为 $maxlen$ ，其对应的后缀位置为 $SA[pos]$ ，即 $P^{maxlen} = suf(SA[pos])^{maxlen}$ ，对于当前位置 $mid$ ，求出 $len = lcp(mid, pos)$ （这可以ST表 $O(1)$ 求出），分类讨论：

  1. $len < maxlen$ ，由匹配的最大性可知 $suf(SA[mid])$ 的第 $len + 1$ 个字符一定不同于 $P$ 的第 $len + 1$ 个字符，直接比较这两个字符即可
  2. $len \ge maxlen$ ，从 $maxlen + 1$ 开始比较 $P$ 和 $suf(SA[mid])$ ，完成后更新 $maxlen$ 和 $pos$
  3. 当 $maxlen = len(P)$ 时，匹配完成

以上过程中， $maxlen$ 是不下降的，加上一个二分，在不考虑预处理的情况下，时间复杂度为 $O(len(P) + \log n)$ （然而，就算是用DC3 $O(n)$ 求出后缀数组，ST表预处理还是 $O(n \log n)$ ）

代码如下：

【模板】AC自动机（简单版）

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
156
157
158
159
160
#include <bits/stdc++.h>
#define STC static
using namespace std;
const int N = 3e6 + 5, D = 30; //开大点
int n;
char T[N], P[N], s[N];
int sa[N], rk[N], hei[N];
struct ST
{
	int mn[N][D];
	int log_2[N];
	void prev(int x[])
	{
		log_2[1] = 0;
		for (int i = 2; i <= n; ++i)
			log_2[i] = log_2[i >> 1] + 1;
		for (int i = 1; i <= n; ++i)
			mn[i][0] = x[i];
		for (int j = 1; j <= log_2[n] + 1; ++j)
			for (int i = 1; i <= n - (1 << j) + 1; ++i)
				mn[i][j] = min(mn[i][j - 1], mn[i + (1 << (j - 1))][j - 1]);
	}
	int ask(int l, int r)
	{
		int t = log_2[r - l + 1];
		return min(mn[l][t], mn[r - (1 << t) + 1][t]);
	}
} st;
void get_sa(int _num)
{
	STC int x[N], y[N], c[N];
	for (int i = 1; i <= n; ++i)
		++c[x[i] = T[i]];
	for (int i = 2; i <= _num; ++i)
		c[i] += c[i - 1];
	for (int i = n; i >= 1; --i)
		sa[c[x[i]]--] = i;
	for (int k = 1, num; k <= n; k <<= 1)
	{
		num = 0;
		for (int i = n - k + 1; i <= n; ++i)
			y[++num] = i;
		for (int i = 1; i <= n; ++i)
			if (sa[i] > k)
				y[++num] = sa[i] - k;
		for (int i = 1; i <= _num; ++i)
			c[i] = 0;
		for (int i = 1; i <= n; ++i)
			++c[x[i]];
		for (int i = 2; i <= _num; ++i)
			c[i] += c[i - 1];
		for (int i = n; i >= 1; --i)
			sa[c[x[y[i]]]--] = y[i], y[i] = 0;
		swap(x, y);
		x[sa[1]] = num = 1;
		for (int i = 2; i <= n; ++i)
			x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) ? num : ++num;
		if (num == n)
			break;
		_num = num;
	}
	for (int i = 1; i <= n; ++i)
		rk[sa[i]] = i;
}
void get_hei()
{
	int k = 0;
	for (int i = 1; i <= n; ++i)
	{
		if (rk[i] == 1)
			continue;
		if (k)
			--k;
		int j = sa[rk[i] - 1];
		while (i + k <= n && j + k <= n && T[i + k] == T[j + k])
			++k;
		hei[rk[i]] = k;
	}
}
int lcp(int x, int y)
{
	if (x == y)
		return n - sa[x] + 1;
	if (x > y)
		swap(x, y);
	return st.ask(x + 1, y);
}
char* suf(int x)
{
	return T + x - 1; //减1是为了让下标从1开始
}
int find(char *x)
{
	int l = 2, r = n, m = strlen(x + 1);
	int pos = 1, mxl = 0; //pos初值不能为0,否则ST表会RE
	char *t = suf(sa[1]);
	while (mxl < m)
	{
		if (sa[1] + mxl > n || t[mxl + 1] != x[mxl + 1]) //为防止越界
			break;
		++mxl;
	}
	if (mxl == m)
		return pos;
	while (l <= r)
	{
		int mid = l + r >> 1;
		int len = lcp(mid, pos);
		t = suf(sa[mid]); //这里一定是sa[mid]不是mid
		if (len >= mxl)
		{
			len = mxl;
			pos = mid;
			while (len < m)
			{
				if (sa[mid] + len > n || t[len + 1] != x[len + 1]) //为防止越界
					break;
				++len;
			}
		}
		if (len == m)
			return pos;
		else if (sa[mid] + len > n || x[len + 1] > t[len + 1])
			l = mid + 1;
		else
			r = mid - 1;
	}
	return -1;
}
int main()
{

	int q, ans = 0;
	scanf("%d", &q);
	for (int i = 1, cs = 0; i <= q; ++i)
	{
		char ch = getchar();
		while (ch < 'a' || ch > 'z')
			ch = getchar();
		while (ch >= 'a' && ch <= 'z')
			s[++cs] = ch, ch = getchar();
		s[++cs] = '$';
	}
	scanf("%s", T + 1);
	n = strlen(T + 1);
	get_sa('z');
	get_hei();
	st.prev(hei);
	for (int i = 1, cs = 1, j; i <= q; ++i)
	{
		for (j = 1; s[cs] != '$'; ++cs, ++j)
			P[j] = s[cs];
		++cs;
		P[j] = 0;
		if (find(P) != -1)
			++ans;
	}
	printf("%d\n", ans);
	return 0;
}

然鹅过不了加强版

求本质不同的子串个数

这当然可以 SAM 做到 $O(n)$ ，但也可上 SA

考虑到每个子串一定是某个后缀的前缀，直接用 $\frac{n(n + 1)}{2}$ 减 $\sum_{i = 2}^n hei[i]$ 即可， $O(n \log n)$

判断最长的不重复的出现

二分长度 $len$ ，把 $lcp \ge len$ 的连续 $hei$ 划分成一段，直接 RMQ 可得这一段的最大/最小下标，若距离大于 $len$ ，就有长度为 $len$ 的串出现两次，时间 $O(n \log n)$

等等

我懒得写了，反正都差不多是用 $hei$ 搞，时间都是 $O(n \log n)/O(n \log^2 n)$ 的样子

神奇的例题

都是从 OIWiKi 上找的

T1

字符加密

板子，复制一份后就是后缀排序

T2

Milk Patterns G

比较板，直接上 SA ，查询每 $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
#include <bits/stdc++.h>
const int N = 2e4 + 100;
int n, num, s[N], ans = 0;
namespace SA
{
    const int D = 16;
    int sa[N], rk[N], hei[N], mn[N][D], lg2[N], len;
    int x[N], y[N], c[N]; 
    template<typename T>
    void get_sa(T s[], int _len, int mxv)
    {
        len = _len;
        int i, k, nxv;
        for (i = 1; i <= len; ++i) ++c[x[i] = s[i]];
        for (i = 2; i <= mxv; ++i) c[i] += c[i - 1];
        for (i = len; i; --i) sa[c[x[i]]--] = i;
        for (k = 1; k <= len; k <<= 1)
        {
            for (nxv = 0, i = len - k + 1; i <= len; ++i) y[++nxv] = i;
            for (i = 1; i <= len; ++i) if (sa[i] > k) y[++nxv] = sa[i] - k;
            memset(c + 1, 0, mxv << 2);
            for (i = 1; i <= len; ++i) ++c[x[i]];
            for (i = 2; i <= mxv; ++i) c[i] += c[i - 1];
            for (i = len; i; --i) sa[c[x[y[i]]]--] = y[i], y[i] = 0;
            std::swap(x, y);
            x[sa[1]] = nxv = 1;
            for (i = 2; i <= len; ++i) x[sa[i]] = y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k] ? nxv : ++nxv;
            if (nxv == len) break;
            mxv = nxv;
        }
        for (int i = 1; i <= len; ++i) rk[sa[i]] = i;
    }
    template<typename T>
    void get_hei(T s[])
    {
        for (int i = 1, j, k = 0; i <= n; ++i)
        {
            if (rk[i] == 1) continue;
            if (k) --k;
            j = sa[rk[i] - 1];
            while (i + k <= len && j + k <= len && s[i + k] == s[j + k]) ++k;
            hei[rk[i]] = k;
        }
    }
    void prev()
    {
        lg2[1] = 0;
        for (int i = 2; i <= len; ++i) lg2[i] = lg2[i >> 1] + 1;
        for (int i = 1; i <= len; ++i) mn[i][0] = hei[i];
        for (int j = 1, t = lg2[len]; j <= t; ++j)
            for (int i = 1; i <= len - (1 << j) + 1; ++i) mn[i][j] = std::min(mn[i][j - 1], mn[i + (1 << (j - 1))][j - 1]);
    }
    int lcp(int i, int j)
    {
        if (i == j) return len - sa[i] + 1;
        if (i > j) std::swap(i, j);
        ++i;
        int t = lg2[j - i + 1];
        return std::min(mn[i][t], mn[j - (1 << t) + 1][t]);
    }
}
using namespace SA;
int main()
{
    scanf("%d %d", &n, &num);
    int mx = 0;
    for (int i = 1; i <= n; ++i) scanf("%d", &s[i]), mx = std::max(s[i], mx);
    get_sa(s, n, mx), get_hei(s), prev();
    for (int i = 1; i + num - 1 <= n; ++i) ans = std::max(ans, lcp(i, i + num - 1));
    printf("%d\n", ans);
    return 0;
}

T3

优秀的拆分

kmp / hash 的做法比较显然，这里讲 kmp ，考虑统计以每个位置开头的 $AA$ 型串的个数记为 $st[i]$ ，就是对于每个后缀做一次 kmp ，由此求出其最短循环节即可统计（直接扫过去判断即可）；然后再做一遍扫描每一个 $AA$ 型串计算其贡献， $O(Tn^2)$ ，只有最后一个点过不了（感觉 3000 元的做法麻烦了，但用的 kmp 的性质还是很优美的）

现在思考这个方法的瓶颈，再于两个方面：求 $st[i]$ 和扫描每一个 $AA$ 型计算贡献；其中第二个好解决：只要再求一个 $ed[i]$ 表示以每个位置结尾的 $AA$ 型串的个数即可，问题在求 $st[i]$ （ $ed[i]$ 类似）

发现 $AA$ 串有 $O(n^2)$ 个，所有计算具体的 $AA$ 串的方法一定是错的；我们考虑反过来枚举 $AA$ 串中 $A$ 的长度 $len$ ，对于每个 $len$ ，我们每隔 $len$ 取一个关键点，这里的时间是调和级数可以当作 $O(n \log n)$

我们发现每一个 $AA$ 一定跨过两个相邻关键点，我们枚举这两个相邻关键点，由 SA 可以 $O(1)$ 得到它们的 LCP 和 LCS ，然后，结论是，存在跨过这两个关键的 $AA$ 的充要条件是 $LCP + LCS \ge len$ ，证明比较简单，看图就能懂：

LCP+LCS

图中染色部分（蓝色和绿色）的任何一个长度为 $2len$ 的子串都是满足条件的 $AA$ （但要保证跨两个点），用差分维护贡献即可求得 $st, ed$ ，一个必须要注意的地方是，我们现在计算的只是长为 $len$ 的 $A$ ，若 LCP 和 LCS 太长，要对 $len/len - 1$ 取 $\min$ 

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
#include <bits/stdc++.h>
#define STC static
using LL = long long;
const int N = 3e4 + 100, D = 16;
int n, lg2[N];
LL st[N], ed[N], ans;
struct SA
{
    int len, sa[N], hei[N], rk[N], mn[N][D];
    char s[N];
    void get_sa(int mxv = 'z')
    {
        STC int x[N], y[N], c[N];
        memset(c, 0, sizeof c);
        memset(x, 0, sizeof x);
        memset(y, 0, sizeof y);
        int i, k, nxv;
        for (i = 1; i <= len; ++i) ++c[x[i] = s[i]];
        for (i = 2; i <= mxv; ++i) c[i] += c[i - 1];
        for (i = len; i; --i) sa[c[x[i]]--] = i;
        for (k = 1; k <= len; k <<= 1)
        {
            for (nxv = 0, i = len - k + 1; i <= len; ++i) y[++nxv] = i;
            for (i = 1; i <= len; ++i) if (sa[i] > k) y[++nxv] = sa[i] - k;
            memset(c + 1, 0, mxv << 2);
            for (i = 1; i <= len; ++i) ++c[x[i]];
            for (i = 2; i <= mxv; ++i) c[i] += c[i - 1];
            for (i = len; i; --i) sa[c[x[y[i]]]--] = y[i], y[i] = 0;
            std::swap(x, y);
            x[sa[1]] = nxv = 1;
            for (i = 2; i <= len; ++i) x[sa[i]] = y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k] ? nxv : ++nxv;
            if (nxv == len) break;
            mxv = nxv;
        }
        for (i = 1; i <= len; ++i) rk[sa[i]] = i;
    }
    void get_hei()
    {
        for (int i = 1, j, k = 0; i <= len; ++i)
        {
            if (rk[i] == 1) continue;
            if (k) --k;
            j = sa[rk[i] - 1];
            while (i + k <= len && j + k <= len && s[i + k] == s[j + k]) ++k;
            hei[rk[i]] = k;
        }
    }
    void prev()
    {
        int i, j, t;
        for (i = 1; i <= len; ++i) mn[i][0] = hei[i];
        for (j = 1, t = lg2[len]; j <= t; ++j)
            for (i = 1; i <= len - (1 << j) + 1; ++i) mn[i][j] = std::min(mn[i][j - 1], mn[i + (1 << (j - 1))][j - 1]);
    }
    void init(int _len, char *_s)
    {
        len = _len;
        for (int i = 1; i <= len; ++i) s[i] = _s[i];
        s[len + 1] = '\0';
        get_sa(), get_hei(), prev(); 
    }
    int ask_rk(int i, int j)
    {
        if (i == j) return len - sa[i] + 1;
        if (i > j) std::swap(i, j);
        ++i;
        int t = lg2[j - i + 1];
        return std::min(mn[i][t], mn[j - (1 << t) + 1][t]);
    }
    int ask_pos(int i, int j){ return ask_rk(rk[i], rk[j]); }
} sas, sat;
char s[N];
void solve()
{
    scanf("%s", s + 1), n = strlen(s + 1);
    sas.init(n, s);
    std::reverse(s + 1, s + n + 1);
    sat.init(n, s);
    memset(st + 1, 0, sizeof(LL) * n), memset(ed + 1, 0, sizeof(LL) * n), ans = 0;
    for (int len = 1; (len << 1) <= n; ++len)
        for (int i = len, j = i + len; j <= n; i = j, j += len)
        {
            int lcp = sas.ask_pos(i, j), lcs = sat.ask_pos(n - i + 2, n - j + 2);
            lcp = std::min(lcp, len), lcs = std::min(lcs, len - 1);
            if (lcp + lcs >= len)
            {
                ++st[i - lcs], --st[i + lcp - len + 1];
                ++ed[j - lcs + len - 1], --ed[j + lcp];
            }
        }
    for (int i = 2; i <= n; ++i) st[i] += st[i - 1], ed[i] += ed[i - 1];
    for (int i = 1; i < n; ++i) ans += ed[i] * st[i + 1];
    printf("%lld\n", ans);
}
int main()
{
    lg2[1] = 0;
    for (int i = 2; i < N; ++i) lg2[i] = lg2[i >> 1] + 1;
    int T;
    scanf("%d", &T);
    while (T--) solve();
    return 0;
}

T4

品酒大会

这题 SAM 、后缀树都可做，但我们用 SA ，我们只求每对后缀的 LCP 贡献，最后搞一个后缀和就是 $O(n^2)$ 的暴力算法；然后发现暴力的瓶颈还是在后缀对的个数太多，考虑到 $lcp$ 的本质是一个 RMQ ，那其实这就是一个类似矩形覆盖的问题

优化方法有很多：单调栈、线段树、并查集……然鹅蒟蒻 Dyd 脑回路清奇打的是（类似）笛卡尔树的东西，但复杂度也并未因此优化，因为求 SA 我只会 $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
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
#include <bits/stdc++.h>
#define fi first
#define se second
#define STC static
using PII = std::pair<int, int>;
using LL = long long;
const int N = 3e5 + 100, D = 20, INF = 0x3f3f3f3f;
int n, a[N];
char s[N];
LL as1[N], as2[N];
namespace SA
{
    int sa[N], rk[N], hei[N], lg2[N];
    PII mn[N][D];
    void get_sa(int mxv = 'z')
    {
        STC int x[N], y[N], c[N];
        int i, k, nxv;
        for (i = 1; i <= n; ++i) ++c[x[i] = s[i]];
        for (i = 2; i <= mxv; ++i) c[i] += c[i - 1];
        for (i = n; i; --i) sa[c[x[i]]--] = i;
        for (k = 1; k <= n; k <<= 1)
        {
            for (nxv = 0, i = n - k + 1; i <= n; ++i) y[++nxv] = i;
            for (i = 1; i <= n; ++i) if (sa[i] > k) y[++nxv] = sa[i] - k;
            memset(c + 1, 0, mxv << 2);
            for (i = 1; i <= n; ++i) ++c[x[i]];
            for (i = 2; i <= mxv; ++i) c[i] += c[i - 1];
            for (i = n; i; --i) sa[c[x[y[i]]]--] = y[i], y[i] = 0;
            std::swap(x, y);
            x[sa[1]] = nxv = 1;
            for (i = 2; i <= n; ++i) x[sa[i]] = y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k] ? nxv : ++nxv;
            if (nxv == n) break;
            mxv = nxv;
        }
        for (i = 1; i <= n; ++i) rk[sa[i]] = i;
    }
    void get_hei()
    {
        for (int i = 1, j, k = 0; i <= n; ++i)
        {
            if (rk[i] == 1) continue;
            if (k) --k;
            j = sa[rk[i] - 1];
            while (j + k <= n && i + k <= n && s[j + k] == s[i + k]) ++k;
            hei[rk[i]] = k;
        }
    }
    void prev()
    {
        lg2[1] = 0;
        int i, j, t;
        for (i = 2; i <= n; ++i) lg2[i] = lg2[i >> 1] + 1;
        for (i = 1; i <= n; ++i) mn[i][0] = {hei[i], i};
        for (j = 1, t = lg2[n]; j <= t; ++j)
            for (i = 1; i <= n - (1 << j) + 1; ++i) mn[i][j] = std::min(mn[i][j - 1], mn[i + (1 << (j - 1))][j - 1]);
    }
    PII lcp(int i, int j)
    {
        if (i == j) return {n - sa[i] + 1, i};
        if (i > j) std::swap(i, j);
        ++i;
        int t = lg2[j - i + 1];
        return std::min(mn[i][t], mn[j - (1 << t) + 1][t]);
    }
}
using namespace SA;
PII dfs(int l, int r)
{
    if (l > r) return {-INF, INF};
    if (l == r) return {a[sa[l]], a[sa[l]]};
    PII t = lcp(l, r);
    int mid = t.se, u = t.fi;
    PII vl = dfs(l, mid - 1), vr = dfs(mid, r);
    as1[u] += LL(mid - l) * (r - mid + 1);
    as2[u] = std::max(as2[u], LL(vl.se) * vr.se);
    as2[u] = std::max(as2[u], LL(vl.fi) * vr.fi);
    return {std::max(vl.fi, vr.fi), std::min(vl.se, vr.se)};
}
int main()
{
    scanf("%d %s", &n, s + 1);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    get_sa(), get_hei(), prev();
    memset(as2, 0xcf, sizeof as2);
    dfs(1, n);
    for (int i = n - 2; ~i; --i) as1[i] += as1[i + 1], as2[i] = std::max(as2[i], as2[i + 1]);
    for (int i = 1; i <= n; ++i) printf("%lld %lld\n", as1[i - 1], as1[i - 1] ? as2[i - 1] : 0);
    return 0;
}

T5

差异

据说是 SAM 的经典题，所以就选了，然而和上题不是一样的吗？笛卡尔树上统计一下就好，感觉是类似双倍经验的东西