哈希

\(\;\)

多项式哈希

\(\;\)
注意hash的时候，每种字母的值不能写成\(s-'a'\)，这样会导致'aaa'和'aaaaa'两种字符串是一样的

矩阵哈希

\(\;\)
把a-z每种字符看成一个\(2\times 2\)的矩阵，这里矩阵内的值都是随机的
一个字符串的哈希值就是\(G_0\times G_1^2\times...times G_{len-1}^{len}\)
这样可以处理一个可重字符串集合判断重复的问题
比如说：\(\{'ab','cd'\}\)和\(\{'ad','cb'\}\)
因为多项式哈希一种字母的值只和它处在字符串中的位置相关，所以在这里无法判断

CF1017E

\(\;\)
让两个凸包旋转、平移同构，那哈希的时候自然就要记一些与旋转、平移无关的量
这里考虑相邻三个点所构成三角形的三条边的长度记一下
那么这样我就会得到一个长度为\(3n\)的序列
这样只需判断是否循环同构就行了

UOJ552

\(\;\)
很妙的一道题
相当于我们要找到一个字符串，使得他在集合1,2的出现次数不等
每张有向图相当于可重字符串集合（可以联想到矩阵哈希）
首先考虑怎么去算答案，我们首先枚举长度，判断长度只要看一下这种长度的字符串集合是否相同
但这里集合非常的大，显然不能一个一个算。
于是考虑dp
就大概\(f_{u,i}=\sum f_{v,i-1}\times G_c\)，c是u，v边上的字母
好找到l后
考虑确定字典序最小的字符串。
我们从小到大填前缀s，每次相当于看一下，是否存在一个字符串是以s为前缀的，且在两个图中的出现次数不同
那我们直接把所有前缀为s的字符串的集合拿出来，只要这两个集合不一样，就代表存在一个字符串是不同的。
那么就只需要统计有多少个是以\(u\)的终点，在组合上一个\(l-len(s)\)就可以了
且答案的字符串不会很长

kmp

NOI2014动物园

\(\;\)
正常kmp的nxt是由\(nxt_{i-1}\)算出来的
但这里要求border的长度不可能超过一半
所以处理nxt的时候自然也不用处理超过一半的情况了，直接把这种情况丢掉

exkmp

\(\;\)
这玩意是可以求对于任意一个\(i\)与前缀的lcp的！！！（md考试的时候坑死我了）
看当前nxt覆盖到最往右的位置，如果越过了\(i\)，就可以采取一些等量代换的方式求，否则暴力往右走

一道回文串的题

\(\;\)
一开始有人说把两个字符串接起来求回文串（这个思路记一下，虽然在这道题没什么用）
考虑将T翻转一下，那么它也变成了选一个后缀的前缀。
而构成回文串，假设回文中心在S中，肯定满足S和T在这个后缀的前缀相等，且S前缀的后面挂着一个回文串
那就不妨求出S,T的lcp，然后在预处理每个点为起点的回文串的个数
一次询问相当于就是个区间加（lcp的那段区间）

AC自动机

构建

\(\;\)
实际就是kmp+trie
但注意它的fail指针并不是找的最长border，而是找其最长的后缀满足是一个模式串的前缀
如果已经求好了\(u\)的fail指针，那么它的\(c\)儿子的fail，就应该看\(u\)的fail的\(c\)指针
如果\(u\)没有c这个儿子，直接将它的儿子连向\(u\)的fail的c指针。
这两种都连的原因是：我可以在不能匹配和可以匹配时，都可以跳它在树上的最长后缀

BJOI2017 魔法咒语

\(\;\)
在做这种字符串子串的问题时，往往要确定让谁去匹配谁，即确定母串和模式串
这里要求若干个\(s\)拼起来，\(t\)在其中不出现。
很明显，这里应该让\(t\)去匹配\(s\)（因为要让t在s中不出现，相当于反子串），也就是说把\(t\)建成AC自动机，把\(s\)在上面跑
而跑的过程，相当于t在s中匹配的过程。那么在过程中，一定不能走到\(t\)代表的终止点
不妨预处理出AC自动机上的每个节点+一种\(s\)字符串，会转移到哪个节点/会不会走到t
设\(f_{i,j}\)表示已经匹配了\(i\)的长度，走到AC自动机上\(j\)的位置
显然最多有50种转移方式，且能写成\(f_{i-1,k}\times g_{k,j}\)的形式，于是可以用矩阵ksm优化

CF86C

\(\;\)
这里要让我们填的串显然就是母串，而s就是模式串
把\(S\)内的字符建AC自动机
在上面跑的过程相当于不断填字符的过程
显然可能走的过程中可能有一段时间不会碰到关键点
所以记录\(f_{i,j,k}\)，这里\(k\)就是最早还没有覆盖的地方是\(k\)
转移就好了

CF1110H

\(\;\)
先考虑统计模式串在母串的出现次数
相当于是在AC自动机上每走到一个关键点，相当于母串中构建出了其中一个子串满足是模式串
但还要注意，还要同时贡献它所有后缀的关键点
相当于我们加一个字符，可能同时会构建出很多后缀，满足这些后缀能模式串匹配。
如果老老实实建AC自动机，节点数太大了存不下。
这里换种方式，直到填到一个数字后，后面不管填啥，都是合法时，才贡献。
相当于我只需要匹配通配符前面的那一段，就能贡献，且不能继续匹配，不然会算多次，所以在建AC自动机时，通配符就是空的，就是我们不想让它继续匹配
预处理每个点的通配符的集合

后缀数据结构

\(\;\)
后缀数组就不多说了吧，很多用途基本上都可以被SAM吊打。

后缀树

\(\;\)
就是把字符串s的所有后缀取出来插入到一颗trie树上。
这样发现两个后缀在树上end的lca就是后缀的lcp
但这样树的大小最坏到\(O(n^2)\)级别
就需要后缀自动机辅助建压缩后缀树

后缀自动机（非常牛逼的一种算法）

构造

\(\;\)
这里不多说了。
后缀自动机上有两种边：转移边、parent边
每个节点里存储的是一个类（拥有同样的right集合），相当于在字符串中在同一些地方出现
并且一个点通过向前的parent边相当于不断删掉前面的字符。
那么最重要的就是发现出现一些前面一些乱七八糟的字符加上这个后缀时，就要拆点，满足跳par边就是不断删前面字符的性质

一些优美的性质

\(\;\)
起点到终点的每一条路径，代表原串的所有本质不同的后缀
从起点到（不一定是到终点）后缀自动机上所有点的路径，代表原串的所有本质不同的子串。
而且每种本质不同的子串，只会唯一对应一条路径
把反串的后缀自动机建出来，其parent树就是原串的后缀树
可以理解为反串的子串在前面不断加字符的过程，就相当于后缀树枚举一个后缀往下建树的过程

基础问题

\(\;\)
求本质不同子串第k小
求路径条数，一遍dp
求不同子串个数第k小（只要位置不同就算不同）
显然这里我们每走到一个点，对应的串可能会在原串中出现很多次。
原先求本质不同时，只会算上一次，但这里我们要加上其在串中出现的次数（相当于这类的串一下会贡献\(r_i\)个串）
求S,T的最长公共子串
把T建出来，S在上面跑，相当于让T的子串和S匹配，匹配的尽可能的长就代表公共子串尽可能的长。
匹配不了就跳par边
最小循环表示
建出来后，跑长度为n的路径，贪心的选小边跑，因为我们可以选前半部分，一定能跑到\(n\)的长度

Problem 1

\(\;\)
询问每个字符串有多少个非空子串是所有\(n\)个字符串的至少\(k\)个的子串
发现这道题是"A的子串是B的子串"，也就是它们有公共的子串
容易想到把\(n\)个字符串建出SAM，让一个字符串s在上面匹配的时候，看到匹配了t，有干两种事情的可能
第一种：s的出现次数加上right集合的大小，
第二种：t出现的次数+1
但我们一定会干第二种，而决不能干第一种
因为一种子串可能在同一种字符串出现了多次
而第二种，在SAM跑到同一个节点时，这里很方便处理。
因为s中的只能算一次，就把节点和fail链上的+1改成赋值为1
打上个标记（多个标记只算一次），然后一遍dfs求解

Problem 2

\(\;\)
求包含\(i\)在s中只出现过一次串中最短的一个
建个SAM，肯定只会考虑在SAM上的叶子节点
我们对于叶子节点里的字符串集合，考虑其贡献。
相当于是一段公差为-1的等差数列和一段相同的数对一段区间取min
这个把操作离线下来，从左往右扫的过程中用堆去维护，因为公差都是-1，所以在全局维护标记\(k\)，代表堆中所有数实际的值实际上是减去k的结果

AHOI2013 差异

\(\;\)
后缀树建出来，就变成两两的lca的深度之和，一遍dfs解决
加强版：求每个后缀和其它后缀的lcp之和
还是那个老套路，插入一个后缀后将其到根的路径上所有点+1
查询是统计到根路径和就可以。

CF235C

\(\;\)
两个字符串循环同构，容易想到复制一遍的套路
这里把T复制一遍比较方便
假设\(len(T)=m\)
然后在跑的过程中，直到跑到的节点所代表的串长为\(m\)才行，加上这个节点的right集合大小就可以了
但我们还要继续匹配，这里有点像kmp的匹配思路，匹配到一个后跳nxt，放到SAM上就是跳par边

区间出现次数

\(\;\)
统计\([l,r]\)这段区间在s内的出现次数（就是统计这个子串所在的节点right集合大小）
先找到\([1,r]\)的出现位置（肯定在right集合只有\(r\)的叶子到根的路径上）
然后\([l,r]\)相当于在这个前缀的基础上不断删去前面的字符，所以我们倍增找到\([l,r]\)所在节点就可以了

广义SAM

\(\;\)
貌似就是把SAM搬到了trie树上，就是考虑一个点新加儿子后产生的一些新的后缀（过程都差不多）

ZJOI2015 诸神眷顾的幻想乡

\(\;\)
这里有一个套路可以记一下。
对于树上的任何一条路径，一定存在至少2个度数为\(1\)的点\(p\)（叶子和根），使得整颗树以\(p\)为根时是一条直上直下的路径
而统计本质不同的路径（现在已经转化了本质不同的子串）
不能对于每颗trie树分开来做，这样处理不了一种子串同时出现在两个trie的情况
所以整体建个广义SAM做就行

计算SAM上节点的right集合

\(\;\)
用动态开点的线段树去维护right集合，而对儿子right集合取并的过程就是线段树合并。

SAM处理回文串问题

\(\;\)
貌似就是反串放到SAM上跑，只要发现匹配的原串\(G\)的端点\([l,r]\)覆盖了right集合的rmx
那么显然\([l,rmx]\)就是回文串
因为SAM可以处理所有的子串，那么所有的回文串的可能都会被算到