【题目描述】
Byteasar 想在墙上涂一段很长的字符,他为了做这件事从字符的前面一段中截取了一段作为模版. 然后将模版重复喷涂到相应的位置后就得到了他想要的字符序列.一个字符可以被喷涂很多次,但是一个位置不能喷涂不同的字符.做一个模版很费工夫,所以他想要模版的长度尽量小,求最小长度是多少.拿样例来说 ababbababbabababbabababbababbaba , 模版为前8个字符ababbaba,是最小的模板长度。

【输入格式】
输入一行最多不超过$500000$个,最少$1$个小写字符。

【输出格式】
一个数表示最小的模板长度。

有一说一 这题我又不会做

我是听了题解之后还挣扎了半天才理解的

前置知识:KMP
首先 把这个串的$nxt$数组(就是KMP里那个)求出来 然后建出这个串的$fail$树
在这里 我举一个例子来帮助理解这题
设给的串是 aabaaba 显然答案是4 即最小模板为 aaba

$nxt$数组

$fail$树(让每个$i$连向$nxt[i]$)

我根本就不会画图

因为模板串必然是主串的一个前缀 也必然是主串的一个后缀 所以可能的答案只会在$0\sim n$的这条链上(不包括0)
再考虑一个问题 设主串为$s$$fail$树上的一个点$i$对于它子树里的所有点$j$一定满足$s[1\sim i]$是$s[1\sim j]$的一个后缀(有点绕) 为什么?不知道就再回去看看$nxt$数组的定义
所以我们可以等价理解为 当且仅当$j$是$i$子树中的一个节点时,我们可以把$s[1\sim i]$喷涂在$j-i+1 \sim j$的位置上 即喷涂到一段以$j$结尾 长为$i$的区间上

—–分割线 理解之后继续看下面的——–

理解了这个之后 剩下的操作就比较简单了 把$0 \sim n$链上的点全部打上标记 从$0$开始dfs,每次到一个点,遍历它所有的儿子节点 若一个儿子节点被标记了 就表示这是链上的下一个点 把它设为$y$若一个儿子节点没有被标记 那就把它子树中(包括自己)所有的点$j$的$deleted[j]$设为1$deleted[j]=1$表示$s[1\sim y]$这个串不能被喷涂在以$j$结尾的位置上
然后删除的时候顺便维护一下 当前最长的一段连续的$deleted[j]$都为1的有多长 记为$mx$处理完所有子节点后向那个打了标记的子节点继续深搜 每到达一个打了标记的点$x$之后立即判断 若$mx < x$即长为$x$的模板已经足够覆盖所有空缺处$x$就是一个符合题意的答案 由于$fail$树的父节点一定比子节点编号小 所以链上第一个$x$就是最小答案

附:样例 程序实现过程

【代码】

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
#include <iostream>
#include <cstdio>
#include <cstring>
#define ri register int
using namespace std;

char ch[500005];
int n, the_nxt[500005];
int head[500005], pre[1000005], to[1000005], sz;
int pr[500005], nxt[500005];
bool mark[500005];
int mx, ans;

void insert(int u, int v) {
pre[++sz] = head[u]; to[sz] = v; head[u] = sz;
}

void del(int x, int fa) {
pr[nxt[x]] = pr[x]; nxt[pr[x]] = nxt[x];
mx = max(mx, nxt[x] - pr[x] - 1);
for (int i = head[x]; i; i = pre[i]) {
int y = to[i];
if (y == fa) continue;
del(y, x);
}
}

void dfs(int x, int fa) {
if (x > mx) return ans = x, void();
int nnxt;
for (int i = head[x]; i; i = pre[i]) {
int y = to[i];
if (y == fa) continue;
if (!mark[y]) del(y, x);
else nnxt = y;
}
dfs(nnxt, x);
}

int main() {
scanf("%s", ch + 1);
n = strlen(ch + 1);
for (ri i = 2, j = 0; i <= n; i++) {
while (j && ch[j+1] != ch[i]) j = the_nxt[j];
if (ch[j+1] == ch[i]) j++;
the_nxt[i] = j;
}
for (ri i = 1; i <= n; i++) {
insert(i, the_nxt[i]); insert(the_nxt[i], i);
}
for (ri i = n; i > 0; i = the_nxt[i]) mark[i] = 1;
mark[0] = 1;
for (ri i = 1; i <= n; i++) {
pr[i] = i-1; nxt[i] = i+1;
}
dfs(0, 0);
cout << ans << endl;
return 0;
}

评论