【学习/出题笔记】失配树瞎吹

原因是做 [POI2005]SZA-Template 这题时新学了fail树,觉得很神的亚子233.

其实本质上就是对于每个前缀 $i$ ,向 $\mathrm{fail}_i$ 连一条边,可以知道这样连出来的一定是一棵 $root$ 为 $0$ 的树。

$1$ LG5829 【模板】失配树

当当当当!是我出的题啦~

给定一个字符串 $s$,定义它的 $k$ 前缀 $pre_k$ 为字符串 $s_{1\dots k}$,$k$ 后缀 $suf_k$ 为字符串 $s_{|s|-k+1\dots |s|}$,其中 $1 \le k \le |s|$。

定义 $\boldsymbol{Border}(s)$ 为对于 $i \in [1, |s|)$,满足 $pre_i = suf_i$ 的字符串 $pre_i$ 的集合。$\boldsymbol{Border}(s)$ 中的每个元素都称之为字符串 $s$ 的 $\operatorname{border}$。

有 $m$ 组询问,每组询问给定 $p,q$,求 $s$ 的 $\boldsymbol{p}$ 前缀$\boldsymbol{q}$ 前缀最长公共 $\operatorname{border}$ 的长度。

发现其实,怎么说呢,从根到某个点的路上的所有点,一定都是它的 $border$。所以就变成了 $lca$ 傻题。然而因为 $border$ 定义的时候不包含整个串,于是再判一下一个是不是另一个 $border$ 即可。

咋说呢,「判断一个点在不在另一个点的子树中」,接到这个问题我居然愣了几秒才想起用 $dfs$ 序搞,wtcl。

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
#ifdef ONLINE_JUDGE
#define freopen(a, b, c)
#endif

#define il inline
#define MAXN 1000005
#define to(k) E[k].to
#define next(k) E[k].next

using namespace std ;

namespace IPT {
const int L = 1000000;
char buf[L], *front=buf, *end=buf;
char GetChar() {
if (front == end) {
end = buf + fread(front = buf, 1, L, stdin);
if (front == end) return -1;
}
return *(front++);
}
}

template <typename T>
inline void qr(T &x) {
char ch = IPT::GetChar(), lst = ' ';
while ((ch > '9') || (ch < '0')) lst = ch, ch=IPT::GetChar();
while ((ch >= '0') && (ch <= '9')) x = (x << 1) + (x << 3) + (ch ^ 48), ch = IPT::GetChar();
if (lst == '-') x = -x;
}

namespace OPT {
char buf[120];
}

template <typename T>
inline void qw(T x, const char aft, const bool pt) {
if (x < 0) {x = -x, putchar('-');}
int top=0;
do {OPT::buf[++top] = static_cast<char>(x % 10 + '0');} while (x /= 10);
while (top) putchar(OPT::buf[top--]);
if (pt) putchar(aft);
}
int ReadStr(char *p) {
auto beg = p;
do *(++p) = IPT::GetChar(); while ((*p >= 'a') && (*p <= 'z'));
*p = 0;
return p - beg - 1;
}
struct Edge{
int to, next ;
}E[MAXN] ; char S[MAXN] ; int fa[MAXN] ;
int head[MAXN], dfn[MAXN], son[MAXN], cnt, tot ;
int H, N, M, dep[MAXN], fail[MAXN], sz[MAXN], top[MAXN] ;

il void add(int u, int v){
E[++ cnt].to = v, E[cnt].next = head[u], head[u] = cnt ;
}
void dfs(int u){
sz[u] = 1, dep[u] = dep[fa[u]] + 1 ;
for (int k = head[u] ; k ; k = next(k)){
fa[to(k)] = u, dfs(to(k)), sz[u] += sz[to(k)] ;
if (!son[u] || sz[to(k)] > sz[son[u]]) son[u] = to(k) ;
}
}
void dfs2(int u, int tp){
top[u] = tp, dfn[u] = ++ tot ;
if (son[u]) dfs2(son[u], tp) ;
for (int k = head[u] ; k ; k = next(k))
if (to(k) != son[u]) dfs2(to(k), to(k)) ;
}
il int lca(int u, int v){
// qw(u, '\n', true), qw(v, '\n', true) ;
// cout << u << " " << v << endl ;
while (top[u] != top[v]){
if (dep[top[u]] >= dep[top[v]]) u = fa[top[u]] ;
else v = fa[top[v]] ;
}
return dep[u] < dep[v] ? u : v ;
}
int main(){
freopen("1.in", "r", stdin);
int i, j = 0 ;
N = ReadStr(S), qr(M) ;
for (i = 2 ; i <= N ; ++ i){
while (j && S[j + 1] != S[i]) j = fail[j] ;
if (S[j + 1] == S[i]) fail[i] = ++ j ;
}
for (i = 1 ; i <= N ; ++ i) add(fail[i], i) ;
dfs(0) ; dfs2(0, 0) ; int p, q ;
for (i = 1 ; i <= M ; ++ i){
p = 0, q = 0, qr(p), qr(q) ;
int ans = lca(p, q) ;
if (dep[p] > dep[q]) swap(p, q) ;
if (dfn[q] >= dfn[p] && dfn[q] <= dfn[p] + sz[p] - 1) ans = fa[ans] ;
qw(ans, '\n', 1) ;
}
return 0 ;
}

长长的 Read 是嫖的zay的233,放到这里算是纪念一下他帮我验题吧!

$2$ [NOI2014] 动物园

定义 $num[i]$ 为字符串 $S$ 的前缀 $S[1\sim i]$ 中不重叠的相同前后缀的个数。给定 $S$,求所有 $(num[i]+1)$ 的乘积。$L\leq 10^6$

发现其实就是 $fail$ 树上,这个点到根的路径上所有 $\leq \frac{L_{now}}{2}$ 的点的编号和。

这东西,那不是随便做?你可以随便上莫队,但是显然过不去;你可以直接剖,可能也不太过得去…不过发现,既然维护一个点到根的信息,那可以直接用栈维护链+dfs=稳得很。所以一眼肯定是二分,不过需要带个 $\log$。

这个地方有一个很nb的trick,可以做到 $O(n)$。根据「二分有可能可以two-pointers」的经典理论,发现随着深度递增,栈内可行的点不降。于是用栈去更新子树信息即可。复杂度 $O(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
void dfs(int x){
(ans *= 1ll * (res + 1)) %= Mod ;
for (int k = head[x], r ; k ; k = next(k)){
stk[++ tp] = to(k), r = res ;
while (stk[res + 1] * 2 <= to(k)) ++ res ;
dfs(to(k)) ; stk[tp --] = 0, res = r ;
}
}
int main(){
cin >> T ;
while (T --){
cnt = 0 ;
memset(fail, 0, sizeof(fail)) ;
memset(head, 0, sizeof(head)) ;
scanf("%s", S + 1), N = strlen(S + 1) ;
for (int i = 2, j = 0 ; i <= N ; ++ i){
while (j && S[j + 1] != S[i]) j = fail[j] ;
if (S[j + 1] == S[i]) fail[i] = ++ j ;
}
for (int i = 1 ; i <= N ; ++ i) add(fail[i], i) ;
ans = 1, res = 0, dfs(0) ; printf("%lld\n", ans) ;
}
return 0 ;
}

$3$ [POI2005] SZA-Template

给定一个串,求一个最小的长度,使得该长度的前缀可以通过循环覆盖覆盖整个串。同一个位置的字符可以覆盖多次。比如 ababa 就可以被 aba 覆盖掉。

$L\leq 10^6$

很神的一道题233

考虑先建出 $fail$ 树来,那么可能成为答案的一定是 $0\sim n$ 这一条链上的点,于是打标记。同时考虑,对于一个 $border$ ,只有两个 $border$ 结尾字符的距离 $\leq$ 该 $border$ 的长度才有可能被算入答案。

考虑怎么维护这个东西,发现对于一段前缀 $[1….i]$,他的所有终点都在他的子树中。于是只需要知道,子树中相邻的点,编号差的最大值,就可以判断是否合法。发现这东西可以直接求前驱和后继,据说有一种暴力可以拿平衡树去维护,然而不是很懂.jpg

考虑从上到下遍历这棵树,那么不断删除不在路径上的子树,更新答案即可。

思考了半天,一直觉得这个算法看不太透。但似乎稍微手玩/思考一下,也没啥大问题。。


嗯,出去吃了个晚饭,编了个自认为很合理的解释:考虑对于一个前缀 $i$,在 $0\sim n$ 的路径上,会对它的判定造成影响的只会是那些包含他但不把他作为 $border$ 的更长的前缀。那么考虑,如果一个前缀不以 $i$ 为 $border$,那么也一定不以 $i+k~(k>0)$ 做 $border$。所以对于一个 $i$ 而言,只需要考虑比他小的 $border$ 产生的贡献,这也正是从根到它的路径上,除去 $0\sim n$ 链之外的所有子树。于是删掉即可。复杂度 $O(\rm |S|)$。

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
struct Edge{
int to, next ;
}E[MAXN] ; int head[MAXN], cnt ;
char In[MAXN] ; int N, fail[MAXN], ans ;
int pre[MAXN], nxt[MAXN], onw[MAXN], val = 1 ;

void del(int x){
// cout << x << endl ;
pre[nxt[x]] = pre[x] ;
nxt[pre[x]] = nxt[x] ;
val = max(val, nxt[x] - pre[x]),
pre[x] = nxt[x] = 0 ;
for (int k = head[x] ; k ; k = next(k)) del(to(k)) ;
}
void add(int u, int v){
E[++ cnt].to = v, E[cnt].next = head[u], head[u] = cnt ;
}
void dfs(int u){
if (val <= u)
return ans = u, void() ; //cout << u << endl ;
int xyg ;
for (int k = head[u] ; k ; k = next(k))
if (onw[to(k)]) xyg = to(k) ; else del(to(k)) ;
dfs(xyg) ;
}
int main(){
int i, j = 0 ;
cin >> (In + 1) ;
N = strlen(In + 1), ans = Inf ;
for (i = 2 ; i <= N ; ++ i){
while (j && In[j + 1] != In[i]) j = fail[j] ;
if (In[j + 1] == In[i]) fail[i] = ++ j ;
}
for (i = 1 ; i <= N ; ++ i) add(fail[i], i) ;
for (i = 1 ; i <= N ; ++ i) pre[i] = i - 1, nxt[i] = i + 1 ;
for (i = N ; i ; i = fail[i]) onw[i] = 1 ;
dfs(0) ; cout << ans << endl ; return 0 ;
}