关于数据结构与算法:数据结构与算法-Manacher-算法

44次阅读

共计 1637 个字符，预计需要花费 5 分钟才能阅读完成。

1 `Manacher`算法

Manacher算法，又叫“马拉车”算法，能够在工夫复杂度为 O(n) 的状况下求解一个字符串的最长回文子串长度的问题。

假如求解的字符串是abcc, 要在其前后插入特殊字符(例如#), 将其转化为#a#b#c#c#c#

咱们用 f(i) 来示意以字符串的第 i 位为回文核心，能够拓展出的最大回文半径，那么 f(i) - 1 就是以 i 为核心的最大回文串长度。为什么呢？通常长度等于 2 倍的最大半径再减去本身反复计算的长度1，即2*f(i) - 1, 然而因为咱们插入了特殊字符#, 一半的字符是特殊字符是不应该算进来的，故而理论长度等于f(i) - 1。

此时以字符串的第 i 位为回文核心，能够拓展出的最大回文右端点 r_m 为$i + $f[$i] - 1;

当咱们计算 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

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

正文完