1 Manacher算法
Manacher算法，又叫“马拉车”算法，能够在工夫复杂度为 O(n) 的状况下求解一个字符串的最长回文子串长度的问题。
2 字符串解决
假如求解的字符串是abcc, 要在其前后插入特殊字符(例如#), 将其转化为#a#b#c#c#c#
2.1 最大回文半径
咱们用 f(i) 来示意以字符串的第 i 位为回文核心，能够拓展出的最大回文半径，那么 f(i) - 1 就是以 i 为核心的最大回文串长度。为什么呢？通常长度等于 2 倍的最大半径再减去本身反复计算的长度1，即2*f(i) - 1, 然而因为咱们插入了特殊字符#, 一半的字符是特殊字符是不应该算进来的，故而理论长度等于f(i) - 1。
此时以字符串的第 i 位为回文核心，能够拓展出的最大回文右端点 r_m 为$i + $f[$i] - 1;
2.2 状态转移方程
当咱们计算 f(i) 时候，就两种状况
状况一：
i <=r_m时候, 阐明此时字符串的第i位被蕴含在i_m为核心能够拓展出的最大回文内，例如上面例子中下标7, 那么此时咱们不必再次核心拓展，因为此时该地位最起码能和其以i_m为核心的对称点f(2*i_m - i)所能拓展出的最大回文相等，毕竟在同一个最大回文嘛，这也是 Manacher 算法的核心思想，记录其对称地位的最大回文半径，那么此地位肯定大于等于其对称地位的最大回文半径 ，我集体了解是有点动静布局的思维，曾经拓展过的，不用再次拓展，只是保留的不是f(i)，而是 i 的对称点f(2*i_m - i)，然而又因为对称点可能向左有拓展， 这边未必能向右拓展，所以对应的f(i) = min(r_m - i + 1, f(2*i_m - i) )，而后再去核心拓展，即状态转移方程就是：$$f(i) = min(r_m – i + 1, f(2*i_m – i) )$$状况二：
i >r_m, 间接f(i) = 1
2.3 #a#b#c#c#c#实例
上面是 #a#b#c#c# 的每一步解决例子：
字符 # a # b # c # c # c # c
下标 0 1 2 3 4 5 6 7 8 9 10 11
半径 f(i) 1 2 1 2 1 2 3 4 4 3 2 1
最右端点 r_m 0 2 2 4 4 6 8 10 11 11 11 11
r_m 对应的 i_m 0 1 1 3 3 5 6 7 8 8 8 8
最大回文串 # #a# # #b# # #c# #c#c# #c#c#c# c#c#c#c c#c#c c#c c 在下标为 7 处，其对称点下标为 2*i_m - i = 2*6 - 7 = 5, 对应的最大半径为min(f(5), r_m - i + 1 ) = min(f(5), 8 - 7 + 1) = min(2, 1) = 1, 则7 至多在 [7,7] 即本身是回文的，而后右边从i - f(i) = 7 - 1 = 6, 左边从i + f(i) = 7 + 1 = 8，向两边拓展，最终拓展到[4,10], 更新i_m = 7, r_m=10
3 PHP 语言形容
public function countSubstrings($s)
{
// 填充特殊字符
$arr = str_split($s, 1);
$s = implode('#', $arr);
$s = '#'.$s.'#';
$len = strlen($s);
$i_m = 0;
$r_m = 0;
$ans = 0;// 不同回文子串的个数，因为退出了特殊字符，故而是 $f[$i]/2，向下取整
$f = [];
$res = [];// 每个地位的最大回文子串汇合
for ($i=0; $i < $len; $i++) {
// 初始化
if ($i <= $i_m && isset($f[2*$i_m - $i])) {$f[$i] = min($r_m - $i + 1, $f[2*$i_m - $i] );
}else{$f[$i] = 1;
}
// 核心拓展
while ($i-$f[$i] >=0 && $i+$f[$i] < $len && $s[$i-$f[$i]] == $s[$i+$f[$i]]) {$f[$i]++;
}
$res[] = substr($s,$i - $f[$i] + 1,2*$f[$i] - 1);
// 更新 $i_m $r_m
if ($i + $f[$i] - 1 > $r_m) {
$i_m = $i;
$r_m = $i + $f[$i] - 1;
}
$ans += floor($f[$i]/2);
}
var_dump($s,$f,$res);
return $ans;
}