字符串
-
难点：理解算法过程
-
二分 + 哈希 可以 $O(n log n) $ 完成 Manacher 和 exKMP
Manacher
P5446
- R 是 S 的一个前缀
- R[1, i] 的后缀的最大回文半径为 r
- 一次翻折：i + r == n 成立
- 多次翻折：目标串合法 且 目标串是一个回文串
- 题解2
exKMP
- \(z[i]\) 表示 \(S\) 和 \(S[i, n]\) 的最长公共前缀
- 流程：见视频
P7114
-
固定 AB 的长度， 随着 i 增加， F(C) 只有两种情况
- C 的前缀中有 2n 个 AB， F(C) = F(i, n)
- C 的前缀中有 2n + 1 个 AB, F(C) = F(1, n)
-
题解1具体实现？
-
题解3
KMP
-
next 数组：最长的【后缀 == 前缀】的长度
P3435
- 最长周期 = i - 最小 next
- 画图理解
P2375
- num ：长度 <= $ \frac{i}{2} $ 的 next 的个数
- 重看 (题解1已掌握)
P5829 失配树
-
i <- next[i] 的关系构成的树
-
为什么是一棵树
- i > next[i]
-
Lca
HDU 7138
- 条件1：[1, x] 是 S 的 border
- 条件2：长度 > i / 2， \(len[i - x + 1, x] = 2x - i\)
- \(2x 和 i 关于 k 同余\)
- 建失配树，条件 1 自然满足
- 条件 2 在树上Dfs
KMP自动机
- 自动机：为给他一个字符串，他能实现一个功能
- 构建（PPT）
- 代码：
Trie
P2922
- 关系
- S 是 T 的前缀
- T 是 S 的前缀
- 字典树
AC自动机
P5357
P2414
P3041
P2444
- 以上重看
选讲
P5329
- 通用方法
- 如果能 \(O(1)\) 判断 si, sj的大小， 就可以重载比较函数， sort
- 设 i < j， k = Lcp
- 转化为 s[i + k + 1] 和 s[j + k] 的大小关系
- ？？？
ICPC
- 暴力：\(n^3\) DP
- 状态2维， 转移
- ？？？
P3426
二分一个前缀作为印章
O(n) Check （好像没法O(n) ?）
-
f(i) 为印出前缀 i 的最小印章长度
-
印章既是前缀，又是后缀（类似border）
-
中间不确定
-
两个结论
- f(i) = i 或 next(i) （？？不能是next[next[i]]？）
-
？？？重看