回文串基础

Algorithm

July 03, 2023

前言

讨论回文串的相关基础问题以及收集寻找本质不同回文串或最长回文串的各种算法。

概念基础

回文串（Palindrome），就是一个符号序列，它正着读和反着读都是相同的。

也就是说回文串总是对称的，奇数长度的回文串在中间的字母上对称，而偶数长度的回文串在两个字母的空儿上对称。

对称是回文最主要的性质，求解过程通常都要分奇数轴和偶数轴分别讨论。

本质不同回文串

它的一个子问题是，寻找最长回文串。

朴素算法

以考虑模式串上的每个位置作为对称轴，对两边的字符进行比对，分奇数轴和偶数轴两种情况。

时间复杂度为 $O(n)$ 。

Rust 实现

/// O(n^2) -> (Odd, Even)
///
/// for odd length palindrome: "aba", r=2
pub fn find_sub_palindromes_brute_force(
    chars: &[char],
) -> (Vec<usize>, Vec<usize>) {
    if chars.is_empty() {
        return (Vec::with_capacity(0), Vec::with_capacity(0));
    }

    let n = chars.len();

    // Odd Symmetry

    let mut d1 = vec![1; n];

    for i in 1..n - 1 {
        let mut matched_r = min(i + 1, n - i);

        for r in 2..=matched_r {
            if chars[i - (r - 1)] != chars[i + (r - 1)] {
                matched_r = r - 1;
                break;
            }
        }

        d1[i] = matched_r;
    }

    // Even Symmetry
    let mut d2 = vec![0; n];

    for i in 0..n - 1 {
        let mut matched_r = min(i + 1, n - 1 - i);

        for r in 1..=matched_r {
            if chars[i + 1 - r] != chars[i + r] {
                matched_r = r - 1;
                break;
            }
        }

        d2[i + 1] = matched_r;
    }

    (d1, d2)
}

串哈希算法

如果只考虑求取最长回文串，可以使用串哈希的方法¹，分别预处理正向的串的哈希和反向串的哈希，实现 $O(1)$ 复杂度的回文串检查，这样对于模式串上的每个位置采用二进制提升（Binary Lifting）的方法，测试出每个位置上的²最长回文串，当然这需要分奇数轴和偶数轴分别求解。

注意当检查子串 $s[i..i+d-1]$ 是否是回文时：

正向的串当然是查询 $i..i+d$ ；
反向串，查询的则是 $n-(i+d)..n-i$

二进制提升的基础是：

对奇数对称的回文，如果有一个半径 $r > 0$ 的回文存在，那么同一个对称轴上必然有一个半径为 $r-1$ 的奇数回文；
对偶数对称的回文，如果有一个半径 $r > 1$ 的回文存在，那么同一个对称轴上必然有一个半径为 $r-1$ 的偶数回；
以上两个定义显然都是递归的

因此假定对每个对称轴上都有一个最大的回文半径，在它范围内的也都是回文，这有有了做二进制提升的条件，这个最大回文半径就是目标，只要仍然构成一个合法回文就是没超过，否则就是超过。

Rust 实现

/// O(nlogn)
pub fn find_longest_palindromes_hash_native<const N: usize>(
    chars: &[char],
    alphabet: &dyn AlphaBet,
    npows: &[[u64; N]],
) -> (usize, Vec<usize>) {
    if chars.is_empty() {
        return (0, Vec::with_capacity(0));
    }

    let p = alphabet.prime();
    let n = chars.len();

    let mut char_ranks = Vec::with_capacity(n);

    for c in chars {
        char_ranks.push(alphabet.rank(*c).unwrap());
    }

    let forward_hash =
        PrefixRollingHash::<N>::new(char_ranks.iter().cloned(), p);
    let backward_hash =
        PrefixRollingHash::<N>::new(char_ranks.iter().rev().cloned(), p);

    // Odd Symmetry

    let max_odd_r = (n - 1) / 2;

    let mut odd_r = 0;
    let mut odd_i = vec![];

    if max_odd_r > 0 {
        for k in (0..=max_odd_r.ilog2()).rev() {
            let r = odd_r + 2_usize.pow(k);

            if r > max_odd_r {
                continue;
            }

            let d = r * 2 + 1;
            let mut found = false;

            for i in 0..n - d + 1 {
                let h1 = forward_hash.query(i..i + d, npows);
                let h2 = backward_hash.query(n - (i + d)..n - i, npows);

                if h1 == h2 {
                    if !found {
                        found = true;
                        odd_r = r;
                        odd_i.clear();
                    }

                    odd_i.push(i);
                }
            }
        }
    }

    // Even Symmetry

    let max_even_r = n / 2;

    let mut even_r = 0;
    let mut even_i = vec![];

    if max_even_r > 0 {
        for k in (0..=max_even_r.ilog2()).rev() {
            let r = even_r + 2_usize.pow(k);

            if r > max_even_r {
                continue;
            }

            let d = r * 2;
            let mut found = false;

            for i in 0..n - d + 1 {
                let h1 = forward_hash.query(i..i + d, npows);
                let h2 = backward_hash.query(n - (i + d)..n - i, npows);

                if h1 == h2 {
                    if !found {
                        found = true;
                        even_r = r;
                        even_i.clear();
                    }

                    even_i.push(i);
                }
            }
        }
    }

    if odd_r >= even_r {
        if odd_r == 0 {
            return (1, (0..n).collect());
        }

        (odd_r * 2 + 1, odd_i)
    }
    else {
        (even_r * 2, even_i)
    }
}

串哈希 DP³

介绍参考串上DP的相关章节

Rust 实现

/// O(n)
pub fn find_longest_palindromes_hash_dp<const N: usize>(
    chars: &[char],
    alphabet: &dyn AlphaBet,
    npows: &[[u64; N]],
) -> (usize, Vec<usize>) {
    if chars.is_empty() {
        return (0, Vec::with_capacity(0));
    }

    let p = alphabet.prime();
    let n = chars.len();

    let mut char_ranks = Vec::with_capacity(n);

    for c in chars {
        char_ranks.push(alphabet.rank(*c).unwrap());
    }

    let forward_hash =
        PrefixRollingHash::<N>::new(char_ranks.iter().cloned(), p);
    let backward_hash =
        PrefixRollingHash::<N>::new(char_ranks.iter().rev().cloned(), p);

    let mut r = vec![0; n];
    r[0] = 1;

    let mut max_d = 1;

    for i in 1..n {
        for d in (1..=min(i + 1, r[i - 1] + 2)).rev() {
            let h1 = forward_hash.query(i + 1 - d..=i, npows);
            let h2 = backward_hash.query(n - (i + 1)..n - (i + 1) + d, npows);

            if h1 == h2 {
                max_d = max(max_d, d);
                r[i] = d;
                break;
            }
        }
    }

    (
        max_d,
        r.into_iter()
            .enumerate()
            .filter(|(_, d)| *d == max_d)
            .map(|(i, _)| i + 1 - max_d)
            .collect(),
    )
}

Manacher 算法

同样介绍参考串上DP的相关章节

Rust 实现

/// return d1
fn find_sub_palindromes_manacher_odd(chars: &[char]) -> Vec<usize> {
    if chars.is_empty() {
        return Vec::with_capacity(0);
    }

    let n = chars.len();

    let mut d1 = vec![1; n];

    let mut pl = 0;
    let mut pr = 0;

    for i in 1..n {
        let mut r = 1;

        if i < pr {
            let j = pl + pr - i;

            r = min(d1[j], pr - i + 1);
        }

        while i + r - 1 < n - 1
            && i - (r - 1) > 0
            && chars[i + r] == chars[i - r]
        {
            r += 1;
        }

        d1[i] = r;

        if i + r - 1 > pr {
            pr = i + r - 1;
            pl = i - (r - 1);
        }
    }

    d1
}

/// return d2
fn find_sub_palindromes_manacher_even(chars: &[char]) -> Vec<usize> {
    if chars.is_empty() {
        return Vec::with_capacity(0);
    }

    let n = chars.len();

    let mut d2 = vec![0; n]; // actual value from 1..n-1

    let mut pl = 0;
    let mut pr = 0;

    for i in 1..n {
        let mut r = 0;

        if i < pr {
            let j = pl + pr - i + 1;

            r = min(d2[j], pr - i + 1);
        }

        while i + r - 1 < n - 1
            && i - r > 0
            && chars[i + r] == chars[i - r - 1]
        {
            r += 1;
        }

        d2[i] = r;

        if i + r - 1 > pr {
            pr = i + r - 1;
            pl = i - r;
        }
    }

    d2
}

pub fn find_sub_palindromes_manacher(
    chars: &[char],
) -> (Vec<usize>, Vec<usize>) {
    let d1 = find_sub_palindromes_manacher_odd(chars);
    let d2 = find_sub_palindromes_manacher_even(chars);

    (d1, d2)
}

统一实现⁴⁵

另外有一种借助字符串构造，利用求奇数轴的单个函数求 $d_1$ 和 $d_2$ 的方法。

这种方法可以这么理解，把原字符串 $s$ 的每个空隙都替换成一个固定字母，比如 '#' ，这样偶数轴的情况就可以由 '#' 字符为对称轴的奇数轴回文得到。

举例：

对于原串 s='abaabaa' ，长度 $n=7$ 。

将空隙替换为字符 '#' 后，得到 s1='a#b#a#a#b#a#a' 长度变为 $2n-1 = 13$ 。

VALUE\ID	0	1	2	3	4	5	6	7	8	9	10	11	12
$s$	a	b	a	a	b	a	a
$s’$	a	#	b	#	a	#	a	#	b	#	a	#	a
$d_1’$	1	1	3	1	2	6	2	1	5	1	2	2	1
$d_1$	1		2		1		1		2		1		1
$d_2$	-	0		0		3		0		0		1

我们可以发现 $d_1’$ 与 $d_1$ 、$d_2$ 有这样的对应关系：

$d_1$ 上的字符对应着 $s’$ 上那些本就属于 $s$ 的字符，分别在 $0,\ 2,\ 4,\ \dots,\ 2i$ ，它的值相比于原来，除了作为轴的那个点外，每额外有一个对称的点，也就额外增加一个插入符 '#' ，因此可以得到：

\[d_1[i] = \lfloor {(d_1'[2i] + 1)}/ {2} \rfloor\]

$d_2$ 上的字符对应着 s’ 上的 '#' ，表示它本来应该是 $s$ 上的字符的空隙，分别在 $1,\ 3,\ 5,\ \dots,\ 2i-1$ ⁶，而 $s’$ 上的值恰好就应该是原来 $s$ 上的两倍，因此可以得到：

\[d_2[i] = d_1'[2i-1] / 2\]

Rust 实现

pub fn find_sub_palindromes_manacher_unify(
    chars: &[char],
) -> (Vec<usize>, Vec<usize>) {
    if chars.is_empty() {
        return (Vec::with_capacity(0), Vec::with_capacity(0));
    }

    let n = chars.len();

    let n2 = n * 2 - 1;
    let mut chars2 = vec!['#'; n2];

    for (i, c) in chars.into_iter().enumerate() {
        chars2[i * 2] = *c;
    }

    let d21 = find_sub_palindromes_manacher_odd(&chars2);

    let mut d1 = vec![1; n];
    let mut d2 = vec![0; n];

    for (i, v) in d21.into_iter().enumerate() {
        if i % 2 == 0 {
            d1[i / 2] = (v + 1) / 2;
        }
        else {
            d2[(i + 1) / 2] = v / 2;
        }
    }

    (d1, d2)
}

补充为回文串

给定一个串，增加一个最小的前缀，使其变为一个回文。

题目

源代码

破题

考虑构建后作为回文的新串与原串的关系，由于要求最小的前缀，那么原串肯定应该至少占据这个回文的右半部分还多一个点，最多占据全部，也就是原串本身就是回文串，这时不需要添加任何前缀。

然后我们可以发现，原串某个前缀因此也应该是一个回文，至少说第一个字符肯定构成长度为 $1$ 的奇数轴回文，此时就是原串占据构造后的回文串部分最少的情况，如果能找到原串属于回文的前缀里最长的那一个，那么显然把那个前缀后面的字符取反后加到前缀上，就能得到一个最小的构造回文。

一般性方法

可以采用朴素地 $O(n^2)$ 的算法，或者前面介绍的 $O(n)$ 地求取所有本质不同子串的方法，然后寻找同时是前缀的最长回文子串，除此之外这里特别介绍一个利用回文反转相同的性质，通过构造字符串利用 KMP 前缀函数求解的方法。⁷

构造串+KMP

回文就是反转后仍然等于原串，那么如果把原串和原串的反转拼接在一起，那么原来是前缀里最长回文的那部分，就会构新串成前后缀相等的情况，长度就是也就是 KMP 前缀数组里 $\pi[n-1]$ 标识的。

有一点需要注意，这里假设得是原串的真前缀是回文，而原串本身不能是回文，否则求解前缀数组的时候就会出现前后缀重叠的情况，可以在构造连接原串和原串的反串时，在中间加一个字母表外的字符，确保不会出现前后缀重叠的情况，比如给定的字母表是小写字母，那就可以加一个 '#' 。

注解

对于朴素串哈希来说，也可以求解本质不同回文串，这里缩小问题是为了方便引出下面的 DP 版串哈希算法 ↩
以该位置为对称轴 ↩
https://oi-wiki.org/string/hash/#%E6%9C%80%E9%95%BF%E5%9B%9E%E6%96%87%E5%AD%90%E4%B8%B2 ↩
https://cp-algorithms.com/string/manacher.html#working-with-parities ↩
https://oi-wiki.org/string/manacher/#%E7%BB%9F%E4%B8%80%E5%A4%84%E7%90%86 ↩
注意，按照我们前面的规定， $d_2$ 采取得是插入序，它的有效值是从 $1$ 开始取的 ↩
但是这道题的测试数据非常宽松，反而是朴素算法的性能最好 ↩

回文串基础

前言

概念基础

本质不同回文串

朴素算法

Rust 实现

串哈希算法

Rust 实现

串哈希 DP3

Rust 实现

Manacher 算法

Rust 实现

统一实现45

Rust 实现

补充为回文串

破题

一般性方法

构造串+KMP

注解

串哈希 DP³

统一实现⁴⁵