后缀数组(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\) 时,所有后缀的排列顺序就是后缀数组。

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

注意到 \(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)\)。
完整代码
| 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;
}
}
输出后缀数组即可。
模板代码
| #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;
}
|
题意
给出长度为 \(n\) 的数字串,求最大相似子串长度,如果没有输出 \(0\)。
相似子串定义为:
- 两个不重叠的子串,差是一个定值;
- 长度 \(\ge 5\);
先对序列进行差分,问题转换为:不重叠出现两次的子串长度最大值。
两个相等的子串可以看作是两个后缀的 \(lcp\),就是 height
数组上的一段区间。然而“不重叠”条件还限制了两个后缀不能离太近。
我们考虑二分答案。先将所有 \(ht[i]\ge mid\) 的位置筛选出来,标记为 \(1\)。如果存在一段连续 \(1\) 的区间中,包含两个相距足够远的后缀,则判定成功。我们只需要记录一段区间中最靠前的后缀和最靠后的后缀即可。
转化为区间最小值
对于一个字符串 \(s\),一些后缀(可以超过 \(2\) 个)的 \(\operatorname{lcp}\) 等价于 height
数组上的一段区间最小值。这是 SA 的一种很常见的手段。
然后,我们就可以使用单调栈统计贡献,使用双指针、可行位置染色等方法求解最优化问题。
代码
| #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;
}
|
题意
给定 \(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
后,要把跨过分隔符的部分全部切除。
代码
| #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;
}
|
题意
字符串的重复次数定义为最大数 \(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
表来维护这段范围内字典序最小的串。后缀数组可以快速比较两个子串的字典序大小。
代码
| #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;
}
|
题意
给定一个长度为 \(n\) 的字符串 \(s\),下标从 \(1\) 开始,保证只包含小写字母。
现在有若干组询问,对于每一个询问,我们给出若干个后缀(以其在 \(s\) 中出现的起始位置来表示),求这些后缀两两之间 \(\operatorname{lcp}\) 的长度之和。
\(n\le 5\times 10^5\)
代码
| #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;
}
|
题意
给出长度为 \(n\) 的数字串,找出出现至少 \(k\) 次的可重叠的最长子串的长度。
代码
| #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;
}
|
题意
给定两个字符串 \(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。
代码
| #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;
}
|
题意
给定一个序列 \(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\) 的区间。后缀排序后找到字典序最小的后缀即可。
边界条件稍微判一下即可。
代码
| #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;
}
|