string theory ​

manacher：
	以i为右端点的最长回文串就是manacher在扩展时第一次访问的串
	例题：（待补）
		最长双回文串
最小表示法：
	处理循环同构子串
kmp，AC自动机，fail树：
	一个神奇的事实：
		将AC自动机像kmp一样实现的复杂度也是对的
		具体见论文：忘了哪一篇
	fail树相关：
		定义：i的父亲是fail[i]，根结点是trie树的根结点
		border定义：若字符串s的某个非空真前缀s[1…i]恰是该字符串的后缀，则称i是s的一个公共前后缀，即一个border
		性质：
			1.点i的最长border是其父亲
			由此可知，点i的所有border就是其所有祖先
			2.点i是点j的后缀等价于j在subtree(i)中（充要性）
			3.点i在点j中出现等价于j的某个前缀是subtree(i)中的点
			由此可知，点i对应的可匹配模式串数量等于其祖先的ed的和
	常见适用范围：
		模式串有多个的类字符串匹配
		对模式串有后缀加和后缀删的操作
Z函数，SA：
	算法功能：
		Z函数就是SA的特殊线性版本
		SA的核心作用就两个：
			求后缀排序
			求任意两个后缀的lcp
	常见适用范围：只有一个串，考虑其子串
	核心思考方向：
		将匹配转化为求lcp
		将子串变为某个后缀的前缀
	后缀排序的应用
		求解第k小子串：P3975
		比较任意两个子串的字典序大小：
			做法一：将所有后缀放进trie树中，再赋上dfs序，比较dfs序即可（时空复杂度平方）
			做法二：求出lcp然后比一下即可
	与字符串匹配的关系
		kmp可以替代Z函数的功能
		SA可以实现kmp，AC自动机的功能：将多个串拼起来即可
		进一步的，SA可以离线回答对模式串前后缀增删后的匹配问题
		例题：
			two strings 罗干 2013中国国家集训队论文答辩
			
			给定两个串，求其最长公共子串

与DP的结合：
	kmp,AC自动机和DP结合：
		方式：将当前匹配的位置设入状态中，转移状态在fail树上找后继即可
		处理：各种涉及到匹配的条件
	Z函数，manacher和DP结合：
		方式：
			将当前的ct和mxr设入状态中，转移时枚举下一次的ct'即可
			可以利用当前mxr，得到对ct'位置的一些性质（例如，border 或 lcp）
		处理：该算法的常见解决问题
例题：
最大化lcp求和
最大化回文求和

循环子串问题：
	串A在S中AA...A的出现，就称A是S的循环子串（非正式定义）
	常见处理办法：
		利用性质：串s由长度为i的循环串组成，等价于s[1~lens-i]=s[i+1,lens]且i整除lens
		常见做法：
			一般先考虑根据题目性质具体分析，再尝试套路做法
			（套路）枚举循环的周期，考虑前后缀匹配，调和级数复杂度（只能处理长度大于等于两倍周期的）
	例题：
		NOI2016 优秀的差分
		NOIP2020 字符串匹配
		lingqingyang:给定一个字符串 s,求重复次数最多的连续重复子串。
类字符串匹配问题：
	当我们看到类似字符串匹配的限制时，可以想办法把原题转化成字符串问题
	以下有常见的几类题型
	
	类回文匹配问题：
		可以套用manacher的思路
		例题：
		给定n*m的矩阵，问有多少个中心对称的子矩阵.lim:n<=5,m<=5e6
		原题是交互
		solution:
		暴力是O(ans)的
		可以发现我们要求的就是某两行的以某一列为中心能对称多长
		考虑到对称，联想到回文，这其实就是manacher
	
	类顺序匹配问题：可以套用kmp,AC自动机，SA的思路
		cf232D Fence:差分转化成字符串匹配问题，然后就是套路DS

manacher：
	以i为右端点的最长回文串就是manacher在扩展时第一次访问的串
	例题：（待补）
		最长双回文串
最小表示法：
	处理循环同构子串
kmp，AC自动机，fail树：
	一个神奇的事实：
		将AC自动机像kmp一样实现的复杂度也是对的
		具体见论文：忘了哪一篇
	fail树相关：
		定义：i的父亲是fail[i]，根结点是trie树的根结点
		border定义：若字符串s的某个非空真前缀s[1…i]恰是该字符串的后缀，则称i是s的一个公共前后缀，即一个border
		性质：
			1.点i的最长border是其父亲
			由此可知，点i的所有border就是其所有祖先
			2.点i是点j的后缀等价于j在subtree(i)中（充要性）
			3.点i在点j中出现等价于j的某个前缀是subtree(i)中的点
			由此可知，点i对应的可匹配模式串数量等于其祖先的ed的和
	常见适用范围：
		模式串有多个的类字符串匹配
		对模式串有后缀加和后缀删的操作
Z函数，SA：
	算法功能：
		Z函数就是SA的特殊线性版本
		SA的核心作用就两个：
			求后缀排序
			求任意两个后缀的lcp
	常见适用范围：只有一个串，考虑其子串
	核心思考方向：
		将匹配转化为求lcp
		将子串变为某个后缀的前缀
	后缀排序的应用
		求解第k小子串：P3975
		比较任意两个子串的字典序大小：
			做法一：将所有后缀放进trie树中，再赋上dfs序，比较dfs序即可（时空复杂度平方）
			做法二：求出lcp然后比一下即可
	与字符串匹配的关系
		kmp可以替代Z函数的功能
		SA可以实现kmp，AC自动机的功能：将多个串拼起来即可
		进一步的，SA可以离线回答对模式串前后缀增删后的匹配问题
		例题：
			two strings 罗干 2013中国国家集训队论文答辩
			
			给定两个串，求其最长公共子串

与DP的结合：
	kmp,AC自动机和DP结合：
		方式：将当前匹配的位置设入状态中，转移状态在fail树上找后继即可
		处理：各种涉及到匹配的条件
	Z函数，manacher和DP结合：
		方式：
			将当前的ct和mxr设入状态中，转移时枚举下一次的ct'即可
			可以利用当前mxr，得到对ct'位置的一些性质（例如，border 或 lcp）
		处理：该算法的常见解决问题
例题：
最大化lcp求和
最大化回文求和

循环子串问题：
	串A在S中AA...A的出现，就称A是S的循环子串（非正式定义）
	常见处理办法：
		利用性质：串s由长度为i的循环串组成，等价于s[1~lens-i]=s[i+1,lens]且i整除lens
		常见做法：
			一般先考虑根据题目性质具体分析，再尝试套路做法
			（套路）枚举循环的周期，考虑前后缀匹配，调和级数复杂度（只能处理长度大于等于两倍周期的）
	例题：
		NOI2016 优秀的差分
		NOIP2020 字符串匹配
		lingqingyang:给定一个字符串 s,求重复次数最多的连续重复子串。
类字符串匹配问题：
	当我们看到类似字符串匹配的限制时，可以想办法把原题转化成字符串问题
	以下有常见的几类题型
	
	类回文匹配问题：
		可以套用manacher的思路
		例题：
		给定n*m的矩阵，问有多少个中心对称的子矩阵.lim:n<=5,m<=5e6
		原题是交互
		solution:
		暴力是O(ans)的
		可以发现我们要求的就是某两行的以某一列为中心能对称多长
		考虑到对称，联想到回文，这其实就是manacher
	
	类顺序匹配问题：可以套用kmp,AC自动机，SA的思路
		cf232D Fence:差分转化成字符串匹配问题，然后就是套路DS