字符串相关算法
hash & KMP & exkmp
Hash
简单的 hash$f(S) = \sum S[i]D^{i-1} \mod P$
代码实现很简单
一般采用双hash
尽量不用 64 位自然溢出
hash 不止可以比较字符串，矩阵也可以
KMP
定义$border$是既是它前缀又是它后缀的串，$fail[i]$表示$S[1,i]$最长的border
怎么算呢，$i-1$的 border 加入一个字符就可以成为$i$的 border
加入一个$T[i]$就是跳 fail 找到使得$S[bor+1] = T[i]$的 border 就可以了。
其实如果$k$是一个 border,那么$|S|-k$就是一个循环节，最短的循环节其实就是$k$取$fail[i]$的时候。
如果循环节长度小于一半就很明显了。 判断循环串就是$|S|$是否被$|S|-fail$的倍数
如果要枚举所有$border$其实就是一直跳$fail$
例题
给定一个无限循环小数的 $N$位，定义一个循环节的置信度就是$ap-bl$,$p$是包含循环节的小数位数，$l$循环节长度，$a , b$正整数系数，求所有循环节最大的置信度
N 1e6
枚举$p$，必然是后缀的$p$位
对于这后$p$位要找最小的周期，这个可以直接$|S| - fail$
定义两个序列$A , B$相似，当且仅当$\forall i,j , (A[i]<A[j]) = (B[i]<B[j])$
并且序列没有重复元素
求$X$有几个连续的子串和$Y$相似
如果$X ,Y$相似，充要条件就是拿掉最后一个数前面的字符串是相似的，并且最后一个数在前面排名一样。
相似是具有传递性的，所以可以直接膜改 KMP
原本是判断$s[x+1] = s[i]$现在就是$s[x+1]$在$s[1,x]$的排名和$i$在$s[i-x,i-1]$的排名是否相同。
其实只要相似具有传递性，这个膜改就很对。
可以用一个主席树类似的东西，反正可以一个$log$做
或者可以考虑 离散化后的 hash 值是否相等
比如考虑我们已经维护好一个序列的 hash 值，我们加入一个数删除一个数，考虑每个数字 rank 是否改变。
$x+1,M$rank++,可以在树状数组维护$D^i$出现的 排名位置 ，然后你要加的就是$D^t$的和 其中$s[t] > x+1$
给定一个串$S$，求每个前缀有多少个 border 满足长度不超过这个前缀一半。
其实就是找一个最大的$border$$j$使得它满足$j \leq \frac i 2$，找到这个就直接$\sum num[j]$
可以直接倍增，或者 DFS 的时候维护一个栈然后二分。但是栈里维护指针是假的，是$O(n^2)$的。 但是这里考虑线性咋做
有一种很直观的做法，对于一个串$S$，如果它的最大 border 长度多余一半，那么它有一个很小的周期，那么一定可以写成$AB^k$形式并且$A$是$B$的后缀。这种情况下$AB^{k-1}$一定是 fail
如果正常的跳border，就是$AB^k \rightarrow AB^{k-1}…\rightarrow A$
如果我们找到周期长度$L = i-fail[i]$，并且我们知道$L \leq \frac i 2$。每次跳起时就是$i \rightarrow i \% L + L$。也就是说我们直接从$AB^k$跳到$AB$
但是有可能会跳过，这个时候就 除法一下就可以正好跳过$\frac 1 2$
可以证明每次至少跳了$\frac 1 3 i$
这样复杂度是$O(n)$的。
本质其实是一个串的$border$可以分成$logn$个等差数列的。 ( border 定理 )
给定一个 Trie ，求每个点到根路径字符串的最长 border，$n \leq 10^6$字符集比较大
维护$go[x][c]$表示$x$搜代表的这个串走$c$后的 fail 所在位置，这个问题求出这个就做完了。
$go[x]$和$go[fail[x]]$的区别是什么呢？区别只有一个，就是$fail[x]$到$x$路径上的第一个儿子。
复杂度大概是$nlogn$字符集可能要用线段树维护
暴力跳$fail$必然是假的，
我们可以每次从$AB^k$跳到$AB$长度至少减去 1/3 所以只跳了 log 次。
CF 1286 E
差分一下，问题变成求所有后缀的权值和，就是所有border权值和
$S[1…i]$的border是KMP树上$i$到 根 的路径。但这样不好维护答案。
如果要维护答案，需要通过数据结构来维护。
维护数据结构，我们发现从$i - 1$到$i$的时候其实是删除了一些 border，剩下的+1。
+1，其实就是$W(L,i-1)$到$W(L,i)$，就是一个取min
但是我们现在要求它删除了哪些border
然后就是要考虑要删除哪些 Border
考虑$i-1,fail[i-1],…,$是$B_1,B_2,…B_m$
要删除的其实是$S[B_k+1] \neq S_i$
把 KMP 树建出来，对于点$x$我们可以把$S[x+1]$看成它的颜色。我们现在要找所有某个颜色。
找出$i - 1 \rightarrow rt$ 的所有颜色为某个东西，就是开一个类似序列自动机的东西维护某个颜色上一次出现的位置，可以$O(k)$找出这条路径。
假设原来是$B_1…B_m$变成了$B_1’…B_k’$删除是$O(m-k)$，每次最多新添加一个 border ，删除的复杂度是$O(n)$的。
数据结构：你需要插入，删除，对所有数求和，所有数对$x$取$\min$这个数据结构直接建 权值线段树就好了。对所有数字取$\min$其实就是删掉前面的很多，然后加入$k$个$x$
ACAM
这里的$fail[x]$是可以到其他串的节点的。
维护$go[x][c]$，表示$x$沿着$c$跳，但是注意这里可能没有$c$这个儿子，记录它最后会跳到哪里。
$go[x][c] = ch[x][c] ? ch[x][c] : go[fail[x]][c]$
给定$n$个字符串，求有多少长度为$L$的字符串$S$使得任意一个$T$都不是$S$连续子串
首先把 ACAM 建出来，然后$f[x][L]$表示当前在$x$长度为$L$的个数。
然后不往结束节点转移就完了。
EXKMP
可以求$S[i,|S|]$与$T$的 LCP。
第一步：求出$S$的每个后缀和$S$的 LCP，然后求$S$的每个后缀和$T$的
假设$D = \max \{i+p_i-1\}$，然后分情况讨论。
具体见温爷爷ppt吧懒得写了。
用处不大，可以$nlogn$后缀数组搞，一般没人卡
后缀数据结构
咕掉了后缀平衡树和一个没听过的东西后缀仙人掌。
后缀排序
两个字符串$A , B$大小比较一般采用字符序，后缀排序一般是给后缀排好序（废话）
大力出奇迹：二分+hash比较$O(nlog^2n)$
实现做法以及用处看这里吧懒得在写一遍了：SA
本质上后缀数组就是后缀树叶子按照dfs序写出来，后缀树就是后缀数组建立的虚树，height就是后缀树相邻叶子的LCA的深度。
本质不同子串个数
子串就是后缀的前缀
为了不算重，我们规定只在最小的后缀算到它
算出来$\sum_{i} n+1-s a[i]-\text {height}[i]$
最小循环表示
这个其实可以On，考虑怎么用后缀数组做
对于$S$的循环表示，其实就是求最小的$SS$的子串
我们可以对$SS$建后缀数组，在$1…|S|$找最小后缀就好了，明显是对的。
求最长的出现了至少$k$次的子串
一个子串所在的后缀数组一定是一个区间，所以答案就是选择一段长度为$k$的连续区间，使得$h$最小值尽量大，直接RMQ
求最长的出现了至少$K$次的子串，并且互不重叠。
可以二分答案$L$，现在要求的就是长度为$L$最多互不重叠出现了多少次
假设出现位置是$P_{1…m}$，一定要满足$|P_i-P_{i+1}| \leq L$
我们可以对$h[i] < L$的空隙切段，剩下的在同一段都可以满足这个条件。
对于每一段，我们从左到右能选多远选多远。
这个贪心很显然吧？
求$S , T$的LCP
拼出一个新的串，相当于从$S$部分选出一个后缀，从$T$选择一个，使得LCP尽量大。
这个很好做。
求 kth 子串
我们知道对于$suf[x]$有$n-x+1-H[rank[x] - 1]$个串被它算到。
可以看这个题解，覆盖了这个问题。
品酒大会
以前用sam写的，可以听一下
我们可以枚举$H$的最小值，找到左边第一个比$H$小的$H_i$，那么这一段之中都比这个大。
大概就做完了。
如果改成$a_x xor a_y$就是 并查集了。
从大到小枚举$H_i$然后就处理两边答案并且把两边并起来。
看起来很通用，做xor的话就需要trie
优秀的拆分
AABB考虑从中间划下来，从$i$划开，然后就是看前面有多少$AA$后缀, 后面有多少$BB$前缀
最后答案就是$\sum pre[i] suf[i+1]$
相当于是对于一个串有多少个$AA$的后缀。
$\frac i 2$是否是$i$的一个 border
把fail树建出来，到每个点记录一下到根的不同长度
$n^2$就这么写完了QWQ 有95分
枚举下长度
我们可以按照长度为$L$分段，使得每个形如$AA$的串必然两次跨越段。$AA$是可以分成两部分的，分别是块的前缀和块的后缀。
假设这两个块的后缀最长是$T$前缀最长是$D$所以要找$0 \leq t \leq T , 0 \leq d \leq D$使得$t + d = L$
大概就酱。
求$S$有多少子串可以改动不超过$K$字符和$T$相等
枚举子串判断
暴力匹配一下，$O(nk)$，匹配不上就跳过
给定$S$把它分割成不超过$m$个连续子串，使得分成子串字典序最大的尽量小
后缀自动机
今天听了ZR 敦爷的课加上以前和zbww讨论了一下，感觉对后缀自动机和后缀数据结构有了船新认识！QWQ
后缀自动机大概分成了下面三部分：
-$n^2$后缀树的构建
- 后缀自动机构建及基础应用
- 缩边并且得到$O(n)$个点的真正的后缀自动机！
后缀树
其实后缀树才是本质的后缀数据结构。
First step 后缀树构建
把单词的后缀插入一棵 Trie 就可以得到后缀树，节点数是$O(n^2)$的。注意，到现在我们还是考虑$O(n^2)$的后缀树。
后缀树上的一个节点其实就对应了一个子串。
其实后缀数组只是后缀树的 DFS 序。
后缀树上点$x$是$y$的祖先，那么$x$明显是$y$的前缀。
一个串$x$出现次数就是它是几个后缀的也就是子树中有多少个后缀点。
显然
一个串在$L$处出现，等价于它是$suf[L]$的前缀，等价于它是$key[L]$的祖先。
显然
那么怎么求$LCP( suf(x),suf(y) )$
前缀关系就是它们的祖先所以就是找$LCA(key(x),key(y))$
本质不同的子串个数
其实就是后缀树的节点个数
最长出现超过$K$次的子串
我们只需要计算每个节点对应出现次数。前面说过了。可以 dfs 一次算出
最长不重叠出现超过$K$次
类似后缀数组二分 L 用$H_i \leq L$割开来算。
也就是说，换在后缀树上，如果$len[x] \leq L$我们就dfs这个子树。
否则如果$len[x] \geq L$我们把子树那的$key$点取出来，排序，然后从左往右能选就选。
求 LCS
把$S , T$拼一起建后缀树。
求一个子串，它在$S$中出现，且在$T$中出现。
也就是说它是$S$某后缀前缀，也是$T$某后缀前缀。
也就是说子树内有$S$的$key$点也有$T$的$key$点。
求第$k$小的子串
按照出边 dfs 下去就好了。
Second step 后缀自动机构建及基础应用
注意，到现在为止还是$O(n^2)$的后缀树！
首先我们拿出一棵后缀树，并且定义：
一个点的$len$表示这个点代表的子串的长度
一个点的父亲（$par[x]$）表示这个点在后缀树上的父亲。
到现在还是后缀树，后缀自动机和后缀树差的其实就是一个 “转移” 数组
-$son[x][c]$在这里后缀树从$x$这个节点代表的子串是往前加字符得到的节点！往后加字符其实构造出来的是前缀树，为了和前面后缀树的拼接我们暂时用$son[x][c]$表示往前加字符的！
现在我们就有了一个基本的后缀自动机。
构建考虑增量法
我们现在有$S$的后缀自动机，考虑往前加入一个字符，怎么整出$cS$的后缀自动机？
步骤大概是：给$cS$这个串建立一个节点，然后给它找到父亲/祖先们，最后整出它的转移。
首先，它的祖先肯定是$cS[1…t]$，这个祖先也有可能不存在，也就是说整个字符串没有$c$这个字母。
我们要先找这个最近的已经存在的祖先（或者是根），再把剩下的祖先建立出来。
首先$cS[1…t]$肯定是$son[S[1…t]][c]$。
如何找到$S[1\dots t]$?很显然的是，$S[1…t]$是$S$的祖先，所以我们可以从$S$向上跳，直到找到$son[x][c]$有值。
然后我们就从$cS[1…t]$往上补全，同时把中间的部分补全，这样我们就构造好了父亲。
然后考虑怎么构造$son$,这些新加进去的点肯定是没有$son$的，如果它加字符还可以连向其他的点，那么它一定是出现过的，即$cS[1…d]$是$S$的一个子串。
考虑什么点的$son$会连向它？其实就是$S$一步步跳到$S[1…t]$中途的点可以通过添加$c$一一对应到这些点。
如果这样的祖先不存在，说明没有$c$出现过，直接从后缀根开始构造就好了。
总结下来一句话，爬链，创链，连链。
Third step 缩边并且得到$O(n)$个点的真正的后缀自动机！
到现在我们的后缀树还是$O(n^2)$节点的，显然是成不了大事的。
这个树叶子数量只有$O(n)$的（后缀数量），也就是说它看起来是非常臃肿。
我们考虑这样的一个事实：如果一个树不存在 只有一个儿子的点 那么点数和叶子数同阶。（画个每个点都至少两个儿子的树就发现是非常显然的了，每次一个点至少合并了两个部分叶子，至少就是$O(2n)$个点）
那么也就是说如果我们可以把只有一个儿子的点压缩了，这就是个线性的树了！
但是我们希望压缩后不会损失信息，所以我们希望 ...- a - a - a -... 这样的树压缩后直接变成了 ... - aaa - ...，最终剩下的点保存的不再是一个串，而可能是几个串。
我们称最后留下来的点叫做关键点。当然叶子还是留着的，我们称之为后缀点。
到这里，发现其实直接对$sa$建虚树和我们最后希望压缩结束的树，本质上是一样的。
但是剩下的关键点，它代表的不再只是一个串了！
所以现在，原来的定义不太适用了，有了新的定义：
定义一个点代表的串的集合是$Z(x)$
同时，$len(x)$的定义也变化了，定义现在是$Z(x)$里面最长串的长度。
然后，定义$fail(x)$就是一个点往祖先爬的第一个关键点，我们也有$|Z(x)| = len(x) - len(fail(x))$。
如何保证一个点被压缩，它的信息仍然留存在关键点上？
现在我们需要证明原树上如果$T$是被压缩的点，那么$son[c][T]$也是被压缩的点
-$cT$是后缀点，那么$T$也是后缀点，矛盾
-$cT$有2个儿子，$cT$也会有两个儿子，矛盾但是如果$x$是一个关键点，$son[x][c]$却可能是被压缩点。
这种情况我们让$son[x][c]$连到它被压缩到的点中。
于是，我们相当于更改了$son$的定义，对于$Y\in Z(x)$，$cY \in Z(son_{new}[x][c])$
这样的话，我们就有了一个无损压缩，既压缩了点又没丢失信息。
怎么构造呢？
回忆一下，刚刚我们构造$n^2$后缀自动机，我们的操作是 爬链，加链，连链（改$son$）
我们能不能更改这个过程，使得构造出来的节点数是$O(n)$的呢？
一样的，假设我们已经对$S$构造出了$O(n)$节点的后缀自动机，加入字符$c$得到$cS$，从$S$所在节点开始爬链。
假设为$cS$新建的点是$P$。
我们假设爬链得到的点是$Q$，$E = son[Q][c]$，也就是说最长的$cS[1…t]$在$E$上 。
但是它可能实际上想链接的是$E$中的某个串在未压缩时所对应的某个子串。根据$fail$的定义是不能把$fail[P]$直接连向$E$的。
如果$len[E] = len[Q] + 1$，想要连接的就是$E$，因为$cS[1\dots t]$就是$E$所对应的最长串长度+1，直接$son[Q][c] = E$就好了，否则如果$len[E] > len[Q] + 1$， 我们需要连接的是一个$Z(E)$中的某个串，方法就是把这个串分裂出来。
假设$Q$想要连接到的串（$Z(E)$中的一个串 ）以及它的 / 存在于$E$的 / 前缀都拿出来建立一个点叫做$k$。现在$E$就相当于被切开了。
于是，$E$的父亲就变成了$k$。
所以把$k$的父亲指向$E$原来的父亲，并且把$E$和$P$的父亲都设置为$k$。
现在爬链不变，加链就变成了拆点，分裂出一个点，从加链变成了加点。
最后还需要更新一下$Q$祖先（包括$Q$）往$c$的转移，即如果有往$c$的转移并且转移向$E$，就把它改成$k$就好了。
基本操作
其实往前加字符和往后加效果是一样的，后面我们就考虑往后加字符了，这样后缀树就变成了前缀树，理解应用的时候更轻松。
再回头看一下$go$数组，可以发现它拥有一个有用的性质：
- 如果$S \in Z(x)$那么$Sc \in Z(go[x][c])$
也就是说，要找到了$T$的节点，其实就是从根出发，按照$T$的字符走$go[x][c]$就好了。
本质不同的子串个数
后缀树的节点个数，就是每个点的$len[x] - len[fail[x]]$的和
一个串的出现次数
其实就是找$key[L]$的祖先，这些祖先含有$[len[fail[x]] +1, len[x]]$个本质不同的子串
最小循环串
找$SS$长为$|S|$的最小子串。
从根开始走了$k$步必然就是一个长度为$k$的子串。
既然找最小，每次走最小的边，走$|S|$次。
如果走到了尽头，那么我们必然走到了一个后缀，但是一个后缀在$SS$中，如果长度不超过$|S|$那么必然可以继续走，所以如果真的走到了死胡同那么当前的大小肯定大于了$|S|$不符合题设。
-$S[L…R]$的定位
$S$必然是$key[R]$的祖先，直接倍增就好了。
求长度为$k$的字典序最小的子串
一个 Trivial 的做法是，走$k$步，每次走最小，这样很容易走到死胡同。
可以求一个$f[i]$表示从$i$开始最长可以走多少步。就是求一个类似拓扑图深度的东西。
求$S,T$有多少对子串相等
$\sum_{x} (cnt_{S,x})(cnt_{T,y})$
可以把这两个串拼起来然后搞后缀树，答案就是对于某个点它子树里面$S$的后缀个数和$T$的后缀个数。
$\sum (len[x]-len[fail[x]]) S(x) T(x)$，$S(x)$表示$x$子树中$S$后缀个数，$T$同理。
本质不同乘的是$[S(x)>0]$
LCS
还是拼起来，搞后缀树，
最长至少出现了 $k$次的子串
对于$x$，求出$x$出现了$S(x)$次，如果$\geq k$就统计就好了
求第$K$小的子串，要求$O(Qn)$
从小到达遍历子串，$F[x]$表示从$x$出发可以走到多少个不同的子串。
设$f(i)$为长度为$f(i)$的子串的出现次数最大值，求 所有$f$，要求线性。
出现次数可以方便地在后缀树上 dp
它可以让长度为$len[fail[x]] + 1 … len[i]$做贡献。
其实可以看成对前缀取max，因为没有
毒瘤：每次往后加$a$，求$T$在$S$出现次数
离线很好做，就是这个题的弱化版 DQS的trie
加一个叶子，把一条边裂开
链加，加叶子，裂边，LCT
给定$n$个字符串，求有几个字符串至少是$K$个串的子串
$\sum |S| \leq 10^5,n,k \leq 100$
对于一个点，我们需要求出它的子树中有无$S_i$的后缀。
这个东西我以前的做法复杂度不可证明，现在老师给了种复杂度正确的做法，
为了保证每个点被一个串抓到，可以这样做，对于每个点到根+1，按照dfs序排序后将两两相邻LCA到根-1。
这样类似虚树地做，假设一个点有$k$个关键点儿子，它会被加$k - (k-1)$次。