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 11r_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; }