1、KMP
1.1、kmp算法需先对模式串建立fail数组，数组所包含的信息就是比如fail[i]表示前缀s[1...i]的最大border长度。
若 0 ≤ r < |s|, pre(s, r) = suf(s, r), 就称 pre(s, r) 是 s 的 border。
也就是当匹配完第i个字符后，假设我们已经到了模式串的第match位，如果S[match+1]！=P[i+1]，则match=fail[match]，转成最大border，使模式串能更快的与匹配串对齐。
利用kmp匹配失败后又再次对齐，就可以解决查找一个串在另一个串中的出现次数（考虑或不考虑重叠）。
1.2、len-fail[len-1]即串中循环节的长度。
1.3、可以做一些和前缀有关的dp，dp[i]=dp[ fail[i] ]+1.
2、最小最大表示法
即求在一个字符串的循环同构体中，哪一个字典序最小/大。
3、stl string
时间复杂度似乎大一点点，但对于暴力是个不错的选择。
4、exkmp
O(N)求一个字符串的所有后缀与另一个字符串的最长公共前缀。
5、manacher
需先预处理成偶数形式（每隔两个字符一个‘#’），令p[i]表示以i为对称中心的回文串的半径，线性扫描处理。
好吧举个例子
aaaabaaaa
假设我们求到了上面那个琥珀色的a，因为我们已经求过b了，所以可知
aaaabaaaa
左右两个是对称的，所以右边琥珀色的a就可以继承左边琥珀色的a的长度，当然也有限制
len=mx>i?min(p[2*id-i],mx-i):1; ，mx为记录的最大右端点值，即b的右端点。
改一改就可以解决凹凸型回文子串问题。