字符串

Hash

用双模数，别64位溢出。会被卡。

KMP

略

例题：[CEOI2011]Matching
- 1.KMP+BIT维护排名 $O(n\log n)$
  2.转化数组后线性KMP $O(n)$ 传送门
例题：动物园：给定一个串 $S$ ，对每个前缀求出它有几个border满足长度不超过这个前缀的一半。 $N\le 10^6$
例题：[HNOI2019] JOJO。求树上KMP。 $N\le 10^6$ ，字符集还蛮大的。
- 法1：
- 法2：
例题：CF1286E。给定字符串 $S$ ，和权值数组 $W$ ，定义 $S$ 的一个子串是好的，当且仅当这个字串等于 $S$ 的某个前缀，一个子串 $S[L:R]$ 的权值是 $W[L,R]$ 的最小值，对于 $S$ 的每个前缀，求他所有好的子串的权值之和。
- 把答案差分，问题转化为求当前位置好的后缀的权值之和。也就是border。考虑加入一个字符，有些border会被扔掉。扔的过程是均摊 $O(n)$ 的。对于剩下的后缀，它们的权值相当于要对一个数取min，直接用数据结构维护。
- 在kmp树（父亲为fail[x]）上找出要删的border（用链表。），在对应数据结构上对应修改。取min就用 $s[w]$ 表示值为 $w$ 有多少个，对 $x$ 取min就把 $>x$ 的所有 $s[w]$ 减去，加到 $s[w]$ 上就完了。顺便维护一下和。

AC自动机

trie上fail。

例题：求长度为 $L$ 不包含任意给定串的字符串数。
- AC自动机上DP，可矩乘。

exkmp

用途： $O(n)$ 求对于 $S$ 的每个后缀与 $T$ 的LCP。
步骤：

对于 $S$ 的每个后缀求出与 $S$ 的LCP，记为 $p[i]$ 。
- 假设已经求出 $p[1...i-1]$ ，要求 $p[i]$
- 设 $D=\max (i+p[i]+1)$ ，满足这样条件的 $i$ 设为 $i_D$
- 则 $S[1:p[i]]=S[i_D:D]$ ，所以 $S[i-i_D+1:p[i]]=S[i:D]$
- 那么有 $min(D-i+1,p[i-i_D+1])\le p[i]$
- 然后暴力扩展。D会变大。所以复杂度是线性。
利用 $p[i]$ 求 $S$ 的每个后缀与 $T$ 的LCP，方法差不多。

后缀数组

略
基本操作：

求LCP(suf[x],suf[y])]：转换成RMQ问题。
求S[L:R]的出现次数：就是LCP>=len的位置个数，一定是Height上连续区间容易计算。
求本质不同子串数：总子串数减去Height之和。
求最小循环表示：倍增找最小长度为|S|的子串。
求最长的出现了至少K次的子串：一个子串所在后缀在后缀数组中一定是一个区间。答案就是选一段长度为K的连续区间，使得H的最小值最大。直接RMQ。
求最长的出现了至少K次的子串，要求不重叠。二分答案L，要求选出尽量多的位置P1到Pm，设任意两个Pi的差大于等于L，且LCP>=L。将H[i]<L的所有空隙切断，因为一定不能经过。那么就在同一段里，从左往右能选就选。
求两个串的LCS。拼起来，加分隔符，选出两边LCP最大的。求出后缀数组随便做。
求第K小子串。求出Height可二分。

例题：

品酒大会。LCP(suf_i,suf_j)>=r,求a[x]a[y]最大。
- 因为Sufx,Sufy的LCP对应的是一个区间的H的最小值，我们可以考虑枚举这个最小值，例如是Hi考虑找到左边第一个比Hi小的HL，以及右边第一个比Hi小的HR，那么对于(L,R]中的X,Y，他们的LCP都大于等于Hi维护个个区间最大值最小值之类的东西就行了
差异：给定字符串S以及权值数组a[1…n]，对于每个r，求满足LCP(Sufx,Sufy)≥r的(x,y)中a[x]a[y]的最大值n≤3×10^5
- 在求出H后，相当于求所有子区间的最小值的和对每个Hi求出左边第一个比他小的和右边第一个比他小的，就能知道有多少个区间的最小值等于他了。
优秀的拆分：对于一个串S，定义一个优秀的拆分是将一个串表示成AABB的形式，求S所有子串的优秀的拆分的拆分个数之和|S|≤2×10^5
- 等价于对每个i求出 $Pre_i$ 和 $Suf_i$ ，表示S[1:i]的AA型后缀个数以及S[i:|S|]的AA型前缀个数，那么答案显然就是 $\sum Pre_i\cdot Suf_{i+1}$
- 枚举一下|A|，把S按|A|切段，对每两段去讨论一下，可以发现只要求lcp就行了。
缺位匹配：求S有几个子串满足改动不超过K个字符就可以和T相等。 $|S|,|T|\le 10^5K\le20$
- 枚举起点，求LCP匹配，遇到无法匹配的跳过继续匹配，最多匹配K次。时间复杂度 $O(|S|K+|S|\log |S|)$
BZOJ4310：给出一个字符串 $S$ ，你需要将它分成不超过 $m$ 个连续子串，使得分割后的所有串的子串中字典序最大的尽量小。
- 二分+从后往前贪心check 博主博客

后缀自动机

0204听课笔记
后缀树

祖先关系

LCA求LCP

基本操作

求最长公共子串时，check节点具体就是看子树内是否都有两个串的后缀。

后缀自动机时间

0204听课笔记
为契合后缀树，所以是反向建后缀自动机。往前加。
构造后缀自动机：

这就是熟悉的后缀自动机板子

上面是ppt内容，此处是总结（转）：

应用

本质不同子串个数： $\sum len[i]-len[fail[i]]$
一个串的出现次数。子树统计。
S[L:R]定位：找一个端点（看是怎么建的SAM），倍增。
最小循环串，SS找长度为|S|的最小子串。建后缀自动机（指正常的后缀自动机，往后面加的）每次走最小的边，走|S|步。肯定不会走不动，因为SS的小于|S|的后缀都是S的后缀。一定能往后走。
找长度为K的最小子串。走K步，每次保证子树深度>=剩下的长度。
求S,T有多少对子串相等：加分隔符串起来，建SAM，用每个串在两边的出现次数乘起来就行了。在某一边出现次数就是子树中某一边的后缀点数。
给定S，T求LCS。同上，找最长两边都出现的节点。
最长出现了k次的子串。同。统计出现次数。
求第K小子串，要求 $O(Qn)$ （忽略字符集）：统计往下面走能得到多少不同子串。然后直接DFS。
EX：要求 $O(Q\log K)$ 比如求长度。（没讲，大概是先考虑暴力DP，k作为DP的第二维，每个点维护可持久化Treap，然后合并Treap）
- SA做法：简单二分。可输出两端点。

总算完了。

开始例题。

品酒大会。
- 与后缀数组，差不多。拆成子树后子树里找最大最小值。
差异。
- 维护子树内后缀点，随便计算。
例题1：设f(i)为所有长度为i的子串中出现次数的最大值。求f(1)~f(|S|)。|S|<=250000，要求线性。
- 枚举点，发现就是区间取max。但是由于f(i)递减。所以左端点没必要，就是前缀取max了。妙。
例题2：维护串S，支持往后加字符，求T在S中出现次数。离线/在线。
- 离线：离线建SAM，即求T在S[1:i]中出现次数。定位T在SAM中节点x。等价于求有几个L<=i-|T|+1且L对应后缀节点在x子树中。
- 在线：发现SAM形态结构为：1.加一个叶子；就是链加。2.把一条边裂开多一个点，直接复制下面哪个点的答案，而且分裂的不会对祖先造成影响因为不是后缀点。然后具体就是用LCT维护一下。
例题3：给定n个字符串，求有几个不同的字符串是至少K个串的子串。Σ|Si|<=10^5，n,k <=100
- 串起来，分隔符，建SAM。枚举点看子树中有多少来自不同串的后缀点。
- 具体方法有：
  - 虚树。某个颜色找出来然后向上贡献。
  - bitset暴力
  - set启发式合并维护有哪些颜色。
例5：
- ，然后用w矩乘。
- 预处理w就枚举b，可以统计一下下面多少串 $go[x][b]=0$ ，
例6：给定字符串 S，对于每个 k，求把 S[k] 变成 # 后，本质不同 s 的子串个数。1e5
- 分类讨论。如果包括#，答案为k(n-k+1)。如果不包含，答案就是 $Sub(pre_{k-1})+Sub(suf_{k+1})-CommonSub(pre_{k-1},suf_{k+1})$ 。两边前后缀各自的子串很好算，建两遍SAM，边建SAM边算就行了；唯一的问题就是求减去那一坨。那么就是要减去出现位置最小值在k左边，最大值在k右边的子串数。对于一个子串x，考虑对哪些k有贡献。枚举 $D\in [len[fail[x]]+1,len[x]]$ ，那么有贡献的区间就是[minL+D,maxL-1]（右端点）。就可以差分。差分后因为是枚举的D。所以减的部分直接单点减，加的部分就是在差分数组上区间加。然后就可以再差分，做到时间复杂度O(n)。
例7：给定字符串 S,T，从 S 中选出子串 s，从 T 中选出子串 t，组成新的串 st，求能组成的串的个数。1e5
- 把组成的串在s长度最大时被计算到。
- 求答案：妙
- 看怎么算 $F[c]$ 。，蛮好理解的。
- 求G：妙。f指下面的子串数。