P8368 [LNOI2022] 串
显然可以发现一种构造方法 $s _ {i, j} \to s _ {i - 2, j - 1}$ 。对于所有长度大于 $1$ 的串，所有 $[1, 1], [2, 2], \ldots, [n, n]$ 均合法，那么 $[1, 2], [2, 3], \ldots, [n - 1, n]$ 均合法。
Algorithm I SA + 链表
- 对于当前合法的 $s _ {l, l + x}$ ，那么 $s _ {l, l + x - 1}$ 是合法的，$s _ {l + 1, l + x + 1}$ 是合法的，那么合法 $l$ 是一个以 $n - x$ 为右端点的区间，且随着 $x$ 增加，区间左端点增加。
- 考虑维护这个区间，为了使得答案最大，如果 $s _ {l, l + x + 1}$ 是合法的，就不必考虑 $s _ {l + 1, l + x + 2}$ 了。
- 如果当前 $[i, j]$ 合法，那么后面同样长度的均合法，$[i + 1, j + 2]$ 也合法，即后面长度为 $j - i$ 的均合法，如果存在 $s _ {l, l + x + 1} = s _ {l’, l’ + x + 1}$ 且 $l’ > l$ ，那么 $[l, l + x + 1]$ 是合法的。
- 考虑如何维护动态的区间的后缀中，是否有相同的串，可以考虑用链表，将排名相邻的连接起来，删除时更新 $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
| #include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
template <class Type>
void read(Type &x)
{
char c;
bool flag = false;
while ((c = getchar()) < '0' || c > '9')
c == '-' && (flag = true);
x = c - '0';
while ((c = getchar()) >= '0' && c <= '9')
x = (x << 3) + (x << 1) + c - '0';
if (flag) x = ~x + 1;
}
template <class Type, class ...rest>
void read(Type &x, rest &...y) { read(x), read(y...); }
template <class Type>
void write(Type x)
{
if (x < 0) putchar('-'), x = ~x + 1;
if (x > 9) write(x / 10);
putchar(x % 10 + '0');
}
const int N = 5e5 + 10;
char s[N];
int pre[N], nxt[N];
int n, m, sa[N], rnk[N], ht[N], x[N], y[N], c[N];
void bucsort ()
{
for (int i = 1; i <= m; ++i) c[i] = 0;
for (int i = 1; i <= n; ++i) ++c[x[i]];
for (int i = 2; i <= m; ++i) c[i] += c[i - 1];
for (int i = n; i; i--) sa[c[x[y[i]]]--] = y[i];
}
void init()
{
for (int i = 1; i <= n; ++i)
x[i] = s[i] - 'a' + 1, y[i] = i, sa[i] = 0;
bucsort();
for (int k = 1; k <= n; k <<= 1)
{
int cnt = 0;
for (int i = n - k + 1; i <= n; i++)
y[++cnt] = i;
for (int i = 1; i <= n; i++)
if (sa[i] > k) y[++cnt] = sa[i] - k;
bucsort();
for (int i = 1; i <= n; i++) y[i] = x[i];
x[sa[1]] = cnt = 1;
for (int i = 2; i <= n; i++)
x[sa[i]] = cnt += (y[sa[i]] ^ y[sa[i - 1]] || y[sa[i] + k] ^ y[sa[i - 1] + k]);
if (cnt == n) break;
m = cnt;
}
for (int i = 1; i <= n; i++) rnk[sa[i]] = i;
for (int i = 1, cur = 0; i <= n; i++)
{
int j = sa[rnk[i] - 1];
if (cur) --cur;
while (s[i + cur] == s[j + cur]) cur++;
ht[i] = cur;
}
}
void del (int x)
{
int l = pre[x], r = nxt[x];
ht[r] = min(ht[r], ht[x]);
pre[r] = l, nxt[l] = r;
}
int main ()
{
int T; read(T);
while (T--)
{
scanf("%s", s + 1);
n = strlen(s + 1), m = 26;
if (n == 1) { puts("0"); continue; }
init();
pre[sa[1]] = nxt[sa[n]] = 0;
for (int i = 2; i <= n; ++i) pre[sa[i]] = sa[i - 1];
for (int i = 1; i < n; ++i) nxt[sa[i]] = sa[i + 1];
int t = 1, l = 1, r = n;
while (t <= n)
{
if (max(ht[l], ht[nxt[l]]) < t) del(l++);
if (l > r) break;
++t;
del(r--);
}
write(t - 1), puts("");
}
return 0;
}
|
Algorithm II SA
考虑从某处 $[l, r]$ 开始，一直以 $[l - 1, r - 2]$ 方式变化，直到 $l = 1$ ，如果使得 $l = 1$ 那么这些都是合法的。如果存在 $s _ {l, r} = s _ {l’, r’}$ ，那么同时存在 $[l, r] \to [l’, r’]$ 的变化方式，在这个过程中 $r - l$ 不断减小，为了使得不因为 $l = 1$ 的原因而不能使答案更大，所有中途不断选择 $[l, r] \to [l’, r’]$ ，直到 $l = r$ ，而在 $[l, r]$ 前也有一定的答案贡献。
故排名相邻的 $j, i$ ，答案贡献为 $height _ i + \frac {n - min(i, j) - height _ i + 1} 2$ 。