データ構造とアルゴリズム:Manacherアルゴリズム

1 ManacherアルゴリズムManacherアルゴリズムは、「マラ車」アルゴリズムとも呼ばれ、時間的複雑度がO(n)の場合、1つの文字列の最長回文サブ列長の問題を解くことができる.
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)を計算すると
ケース1: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))$$
状況2:i >r_m 、直接f(i) = 12.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;
    }