Manacher 回文串算法

Manacher是一个比较简洁的求最长回文串的算法。主要思想仍然是dp。主要思想是：定义d1,d2数组，分别对应于奇数和偶数长的回文串，其中：

d1[i]代表着以i为中心的奇数长的最长回文串的半径,比如aabaac中的d1[2] = 3。对应最长回文串是aabbaa,全长是 2 * d1[2] - 1 = 5
d2[i]代表这是i为中心偶数长的最长回文串的半径，比如说abbac中的d2[2] = 2。对应的回文串是abba, 全长是2 * d2[2] = 4

计算出d1,d2数组也就能求出字符串中所有的回文串的长度。那么d1和d2该怎么求呢？

基本算法

最直接的，我们可以以s[i]为中心，依次比较s[i - k]和s[i + k]是否相等，找到这个最大的k即可求出d1或者d2

万物皆可dp

直接使用基本算法将会使时间复杂度变成O(n^2)，为了让它降低，我们有必要减少一些重复的计算。采用一种dp战术，以空间换时间。

重复计算的场景在于当我们得到一个大的回文串的时候，里边的小回文串可以利用大回文串的镜像特性直接转移到镜像的小回文串上而不需要从头计算。如下图所示：如果我们知道s[l..r]是回文串，那么d[i]就应该直接等于i的镜像点d[l + r - i]

但是如果镜像回文串的范围超出了大回文串，那么超出部分还是需要用基本算法来求：

通过这个思路我们就可以在O(n)的时间复杂度的情况下求出d1和d2

简化技巧

d2和d1的过程基本一致，我们可以通过如下方法来将偶数回文串变化成奇数回文串：在所有字符间隙中插入一个无效字符#，比如说abba将会变成#a#b#b#a#，那么我们就可以具体的把偶数回文串变化为以#为中心的奇数回文串了。而且变化后的半径实际上意义相当于变化前的回文串长度 + 1。无论是奇数还是偶数回文串。

Rust 实现

题目地址： https://www.luogu.org/problem/P4555 AC代码：

use algorithms_in_rust::Scanner;
use std::cmp::{max, min};

fn build_d1(bytes: &Vec<u8>) -> Vec<i32>{
    let mut l = 0i32;
    let mut r = -1i32;
    let n = bytes.len() as i32;
    let mut d1 = vec![0i32;n as usize];
    for i in 0..n {
      let mut k = if i > r { 1i32 } else { min(r - i, d1[(l + r - i) as usize]) };
      while i - k >= 0 && i + k < n && bytes[(i - k) as usize] == bytes[(i + k) as usize] {
          k += 1;
      }
      d1[i as usize] = k;
      // k is represent the length, so delta should - 1 
      let delta = k - 1;
      if i + delta > r {
          l = i - delta;
          r = i + delta;
      }
    }
    d1
}

fn expand(str: &str) -> Vec<u8> {
    let mut s: Vec<_> = vec![b'#'; 2 * str.len() + 1]; 
    let mut i = 1usize;
    for c in str.bytes() {
        s[i] = c;
        i += 2;
    }
    s
}

fn calc(dis: &Vec<i32>) -> i32 {
    let mut l_center = vec![0i32;dis.len()];
    let mut r_center = vec![0i32;dis.len()];
    let mut pos = 0i32;
    let mut res = 0i32;
    for i in 0..dis.len() as i32 {
        while pos < i + dis[i as usize] {
            l_center[pos as usize] = i;
            pos+=1i32;
        }
    }
    pos = dis.len() as i32 - 1;
    for i in (0..dis.len() as i32).rev() {
        while pos > i as i32 - dis[i as usize] {
            r_center[pos as usize] = i as i32;
            pos -= 1;
        }
    }

    for i in 0..dis.len() {
    // if any center distance is 1, the corresponding byte definitly is '#', zero length substring is not acceptable.
        if dis[l_center[i] as usize] == 1 || dis[r_center[i] as usize] == 1 {
            continue;
        }
        res = max(res, r_center[i] - l_center[i]);
    }
    res
}

fn main() {
    let mut scan = Scanner::default();
    let str = scan.next::<String>();
    let bytes = expand(&str);
    let d1 = build_d1(&bytes);
    println!("{}", calc(&d1));
}

详细算法解释： https://oi-wiki.org/string/manacher/

stkevintan / kirk-blog