2018.7 长郡中学集训

OI 笔记

Day 1 字符串

查东西上cplusplus.com

最小循环表示法

回文串

manacher

KMP

ExKMP O(n)求所有后缀和原串的LCP
类似于manacher

trie

AC-automatic

trie图

hash

后缀数据结构

后缀数组 : 倍增法构造

h[i]表示排序后第$i$和$i+1$后缀的LCP,y[i]表示排序前后缀$i$的h值， 由$y[i] \ge y[i-1] - 1$可$O(n)$求后缀LCP
排序后后缀i与j的LCP=min(h[i..j]);(RMQ)

后缀树 : 后缀建trie，压边，节点数不超过2n

用途：
判断是否是子串（可被SAM替代）

自动机 : 增量法构造(背板子)

两部分
1. DAG 一条从根出发的路径等价于一个子串
2. parent树

性质：
- DAG上每个点能识别的串长度是一段连续的区间
- parent树上父亲能识别的串是孩子的后缀

用途：
判断是否是子串

后缀平衡树

动态维护后缀数组？

后缀仙人掌

emmm

应用

1. 统计不同子串个数
   $\displaystyle\frac{n*(n+1)}{2}-sum\{h[]\}$
2. $A$,$B$最长公共子串
   $B$在$SAM(A)$上跑 or 在$SA(A+`\#`+B)$上瞎搞(没听懂)
3. 多串最长公共子串
   都在$SAM(A)$上跑, 每个节点记录与各个串匹配长度的最小值, 答案取每个节点的最大值
4. 两个串有多少个长度>=k的公共子串(位置不同视为不同)
   在$SA(A+`\#`+B)$上瞎搞(没听懂)
5. [NOI2018]你的名字