字符串个人总结
最小循环节
KMP求出Next[]后，第
如果对于next数组中的 i， 符合 i % ( i - next[i] ) == 0 && next[i] != 0 , 则说明字符串循环，而且
循环节长度为: i - next[i]
循环次数为: i / ( i - next[i] )
同理，次小循环节为
长度为N的字符串最多有N个本质不同的回文子串
Trie树的大小，既不能开太大MLE，也不能开太小，防止极限数据卡大小（最大是\Sigma len ），应该看着内存限制开；
模板串
科学家温斯顿从数据库中找到了一串相当长的字符串。他正试图用一个模板串来重构这个字符串。
他可以将模板串复制多份，通过合适的方式拼接起来，使得最终的串与原串一致。
如果两个模板串互相覆盖，那么覆盖的部分必须完全一致。（可以不重叠）
原串的所有位置必须被覆盖到。
显然，原串本身就是一个模板串。但为了节省成本，他想找到长度最短的模板串。
CF17E Palisection 相交回文子串
给定一个长度为n的小写字母串。问你有多少对相交的回文子 串（包含也算相交）。
这道题正着想不好做，考虑容斥：任选两个回文子串-选择两个不相交的回文子串；
选择两个不相交的区间？这种题见过几次了，枚举分割点，前缀后缀各选一个；
但是这道题会算重很多次，考虑优化；
ans+=在这个分割点之前的回文子串×以这个分割点开始的回文子串；
跑一边马拉车，区间加，求单点，转化为前缀和，其中“在这个分割点之前的回文子串”要再做一次前缀和，然后统计答案；
string 定义的<号默认只比较字符的字典序，而不是长度
BZOJ4896 补退选
这道题，没想到如此暴力的做法；属于求啥设啥的典型：直接开vector存每个点出现次数为i的最早时间；这样的空间复杂度是N的；
从特殊到一般
Trie树求与一个数异或的第k小值
类似二分查找；
int query(int v,int k)
{
int x=rt,res=0;
for(ri i=30,cur;i>=0;--i)
{
cur=(v>>i)&1;
if(sz[tre[x][cur]]>=k) x=tre[x][cur];
else k-=sz[tre[x][cur]],x=tre[x][cur^1],res|=1<<i;
}
return res;
}isalpha()的返回值当大写字母返回1，小写字母返回0
字符串题，大部分从暴力想起，然后想Hash、SAM等优化
[JSOI2016]扭动的回文串
枚举对称的位置。则整个回文串一定可以表示为A(i,l)+A(l+1,j)+B(j,k)或A(i,j)+B(j,l)+B(l+1,k)，其中，第一段与第三段对称（第一段正着Hash和第三段反着Hash相同），第二段是一个回文子串，三段都可以是空串。
这道题的关键是在每个对称轴处，以最长的回文串为基础再拓展。原因是若不是最长，则答案不会更优。
此类题注意清空数组！
注意清空Trie树的0号点！
AC自动机应用：
使用AC自动机解决子串包含问题。A包含B的充要条件：A在Trie树上的节点，至少一个的fail树祖先包含B的终止节点。
AC自动机&SAM
由于AC自动机较简洁，往往能更优雅的解决一些问题。
AC自动机可以离线求多个串的每个前缀的LCP：把所有串建AC自动机，则答案是fail树的LCA。