前言

动规类型的题目暂时告一段落了, 现在开始刷字符串相关的题目. 今天做的题是 131. 分割回文串 很自然的想到了回溯算法, 也成功通过了测试. 做完后在看题解的过程中发现针对回文串有一个manacher算法. 具有O(n)的时间和空间复杂度. 比我O(n^2)的解法不知道高到哪里去了. 题解中还列出了四个回文串相关的题目, 于是乎我就学习了一下这个manacher算法, 把剩下的三题也给做了. 在此记录一下.

正文

manacher算法

关于回文串的定义就不再细说, 简单地说就是从右往左和从左往右读都一样. 而manacher算法可以实现这样一个功能: 以O(n)的时间复杂度计算整个字符串中以任意字符为中心的最长回文子串的长度. 比如对于如下字符串

s = "aba"

manacher 算法就可以在 O(n) 时间内计算得到如下数组

arr = [1, 3, 1]

关于manacher算法网上讲的内容已经很多了, 比如这篇题解讲的就挺好的, 不再复述了.

核心思想其实就是复用之前得到的回文子串的信息, 避免重复计算. 贴一下自己rust实现的manacher算法代码吧

/// 马拉车算法, 输入字符串s(长度为n), 算法会再s中插入n+1个
/// '$' 形成 sa, 然后返回一个 长度为n+1的 usize 数组 dp
/// dp[i] 表示sa中以 i 为中心的回文串的最大长度.
fn manacher(s: &String)-> Vec<usize>{
    let n = s.len();
    if n == 0 {return Vec::new();}
    let n = n * 2 + 1;
    let mut sa:Vec<u8> = Vec::with_capacity(n);
    sa.push(b'$');
    for ch in s.chars() {
        sa.push(ch as u8);
        sa.push(b'$');
    }
    let mut dp: Vec<usize> = vec![1; n];
    let mut left=0 as usize;
    let mut right=0 as usize;
    let mut dig_more: bool;
    for i in 1..n {
        let cur: usize;
        if i <= right {
            cur = std::cmp::min(dp[left+right-i], (right-i)*2 + 1);
            if cur == (right-i)*2 + 1 {
                dig_more = true;
            } else {
                dp[i] = cur;
                dig_more = false;
            }
        } else {
            cur = 1;
            dig_more = true;
        }

        if dig_more {
            let mut side = (cur-1)/2;
            while side<i && i+side<n-1 && 
                    sa[i-1-side] == sa[i+side+1] {
                        side += 1;
            }

            if i+side > right {
                left = i-side;
                right = i+side;
            }
            dp[i] = side*2 + 1;
        }
    }
    // println!("{}", String::from_utf8(sa).unwrap());
    // println!("{:?}", dp);
    dp
}

5. 最长回文子串

直接使用 manacher算法计算所有的回文子串的长度, 然后找到最大的就好了.

这儿需要注意的一点就是s和sa之间索引变换关系.

647. 回文子串

题面如下:

给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被计为是不同的子串。

同样是直接使用 manacher算法计算所有的回文子串的长度, 然后累加一下就好了.

131. 分割回文串

这题我是用回溯做的, 学完 manacher 之后是想过用 manacher重新实现的, 但是因为这题需要返回分割得到的字符串数组. 使用manacher相比于用回溯写一些会比较麻烦. 所以就没有再修改了.

132. 分割回文串2

这题我一开始是基于 131 的回溯算法进行修改的. 正确性没有问题, 但是因为时间复杂度太高过不了一个测试用例. 所以选择使用 manacher算法+动规来实. 并过了测试用例.

先根据 manacher 算法的结果生成一个数组lens, lens[i]表示s中以第i个字符作为左边界的所有回文字串的长度.

然后定义一个动态规划数组dp, dp[i]表示s[..i+1]这个字串最少需要切割多少次.状态转移方程如下

dp[i+len] = min(dp[i+len], dp[i-1] + 1)

结语

通过这几道题目又巩固了一下回溯算法. 也学到了一个manacher算法. 之后遇到回文串相关的题目就应该首先想到这个算法. 时间和空间复杂度都很优秀.

因为时间原因本篇博客写的有点水… 不过大致思路应该都讲清楚了.

参考

参考题解