这题我观察出了一些显然的性质，但还是没有做法。（
做完之后，对 SAM 的运用倒是更加熟练了。那个 DP
状态，虽然见过很多回这样的形式了，但还是没想到。
为方便叙述，我们将原串翻转，限制变为 是 的真子串。
性质 1
，即每加一个串，顶多在开头或结尾加一个字符，这是显然的，因为加得越多，后面的串越难合法。
性质 2
设 表示求解 中的问题，且强制让 的右端点为 时最大的 。（实际上就是 最大的长度）
那么 （这里比较的是两个
的左端点的位置，事实上，
所代表的方案，每个串都删一个字符，就能变为 的方案，即 ，故上述性质显然成立。）
这里的 实际上就是 DP
状态，我们考虑维护 所代表的区间
，由性质 可得 是不降的，这启示我们可以双指针。
如何判断一个串
是否合法（即成为某个方案中的
）呢？
根据意义，我们要找到一个串 满足 且 为 去掉开头或结尾且 合法。
此外，若 合法，则 合法 。
考虑使用一个 SAM 维护右端点 的合法串的贡献。设在 SAM 上 所在的结点为 。
那么在双指针的过程中，执行如下算法：
- 设 表示节点 所包含的最长合法子串的长度。
- 当 时，检查当前的
是否合法，即 和 在 SAM 上的点的 的较大值是否 。
- 如果 合法，那么令 ，令 为该串在 SAM 上的节点 。并回到第二步。
- 如果
不合法，那么我们需要在 SAM 上更新
的信息，这个时候
就有用了，因为我们已经将
开头的合法串信息存在了
里。我们先让 与 取 ，再跳 的父亲 ，这个时候 应该变为 。如果当前的 不为 ，就将其置为 ，否则可以直接 break，因为如果 ， 的祖先 也必然满足 了。做完上述过程后，令 ，回到第三步。
另外提一嘴，维护 的节点
，只需要在 增大时让 沿着 DAWG 向下走一步，在 增大时，如果 ，就令 即可。
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
| #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 5e5 + 5,Sz = N << 1;
int n;
int ch[Sz][26],len[Sz],link[Sz],tot = 1,las = 1;
int f[Sz];
char s[N];
int Nd[N],Ans[N];
inline void extend(int c)
{
int cur = ++tot,p = las;
len[cur] = len[p] + 1;
while(p && !ch[p][c]) ch[p][c] = cur,p = link[p];
if(!p) link[cur] = 1;
else
{
int q = ch[p][c];
if(len[p] + 1 == len[q]) link[cur] = q;
else
{
int clone = ++tot;
for(int i = 0;i < 26;i++)
ch[clone][i] = ch[q][i];
link[clone] = link[q];
len[clone] = len[p] + 1;
while(p && ch[p][c] == q) ch[p][c] = clone,p = link[p];
link[cur] = link[q] = clone;
}
}
las = cur;
}
inline void Upd(int p,int v)
{
if(v <= f[p]) return;
f[p] = v;p = link[p];
while(p && f[p] != len[p]) f[p] = len[p],p = link[p];
}
int main()
{
cin >> n;
cin >> (s + 1);
std::reverse(s + 1,s + n + 1);
for(int i = 1;i <= n;i++)
extend(s[i] - 'a');
int l = 1,p = 1,ans = 0;
for(int r = 1;r <= n;r++)
{
int q = p;
p = ch[p][s[r] - 'a'];
while(l < r)
{
if(max(max(f[p],f[q]),f[link[p]]) >= r - l) break;
Upd(Nd[l],Ans[l]);++l;
if(len[link[p]] >= r - l + 1) p = link[p];
if(len[link[q]] >= r - l) q = link[q];
}
Nd[r] = p;Ans[r] = r - l + 1;
ans = max(ans,r - l + 1);
}
cout << ans << endl;
return 0;
}
|
关键在于这个 DP
状态，非常巧妙地把题目中各类性质和对象统一了起来。