647. 回文子串">647. 回文子串

647. 回文子串

题目描述

给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

解题思路

本题是回文子串的原始题型，也是Manacher算法的模板题。Manacher算法是专门用于解决回文子串问题的简单算法，而且具有最小的时间复杂度。

在介绍Manacher算法之前，先简要分析下回文串的性质。形如“a”、“aa”、“aba”的字符串被称为回文串，从左到右读和从右往左读是一样的，可以颠倒顺序，具有中心对称性质，而且回文串是可以从中心往外扩展来构造的。

沿中心的扩展性很容易让人联想到动态规划算法，我第一次做就是用动态规划，但这么做的时间和空间复杂度都为O(N^2)，因此本题不适合用动态规划法。

很明显的一点是，回文串的长度可以是奇数，例如“a”、“aba”，也可以是偶数，例如“aa”、“abba”，此时的中心可以是中心靠左的字符，也可以是中心靠右的字符。

此处有一个小技巧，就是在回文串的前后和每两个字符之间插入“#”，如下所示。原长度为n的字符串，构造后长度为 2n+1 ，还可以保证原来的回文串在构造后都变成了长度为奇数的回文串，不用再分奇偶数讨论。

a b a b a b c ====> # a # b # a # b # a # b # c #

下面进入正题，介绍Manacher算法的细节。

用到的数据结构

设输入串长度为 n ，将输入的字符串扩展后得到长度为 2n + 1 的新字符串 s 。

算法运行期间维护一个回文子串的下标，简记为 (l, r) ，请注意，这是一个左闭右闭区间 : )。该下标用来标记当前找到的最靠右的（右侧下标 r 最大的）回文子串 s[l : r] 。初始情况下，设 l = 0，r = -1 。

算法用数组 p[2n + 1] 维护查找记录， p[i] 记录了以字符 s[i] 为中心、向两边扩展所找到的回文子串的总数。你也可以把它看作是以字符 s[i] 为中心的最长回文子串的半径。数组内的记录总和（记得除以2并向下取整）就是本题的答案。

过程描述

Manacher利用回文子串的对称性质来优化回文串的查找。

算法逐个遍历字符串内的字符，当遍历到下标为i的字符 s[i] 时：

不妨设 l < i < r ，
由于回文子串 s[l : r] 具有对称性，因此字符 s[i] 在回文子串中有一个中心对称的位置，设对称位置的字符为 s[j] ，
如果 p[j] 的值已经计算过了（ i>j 这一点其实可以保证），而且 s[j] 对应的最长回文子串仍然在 s[l : r] 的范围内，那么恭喜！由于回文串的对称性，p[i] 可以直接等于 p[j]，
如果不太幸运，s[j] 对应的最长回文子串超过了 s[l : r] 的范围，那么很遗憾，超过了范围的部分是否为回文是不能保证的，但我们可以保证在范围内的部分一定是回文（对称部分也一定是回文），然后对范围外的部分进行搜索，
下图👇展示了回文串 s[i : j]、以 s[j] 为中心的最长回文串、以 s[i] 为中心的最长回文串，三者之间在理想情况下的关系

下图👇展示了不理想情况下，范围内的部分和范围外的部分之间的关系

用伪代码来归纳以上过程：

for (遍历构造后的字符串) {
    if (s[i]在回文串s[l:r]之外) {
        从中心扩展计算p[i];
    } else if (以s[j]为中心的最长回文串在s[l:r]之外) {
        p[i] = 以s[j]为中心的最长回文串在s[l:r]以内的长度;
        从s[l:r]边界向外扩展计算p[i];
    } else {
        p[i] = p[j];
    }
    更新(l, r);
}

下标细节

字符串和数组问题的棘手之处就在于下标处理。因此在讨论算法的时候我刻意回避了下标运算，而把它单独放在一个section里分析，防止思路拘泥在细节上。

字符 s[i] 在回文子串 s[l : r] 内对称位置的下标 j = l + r - i 。

以字符 s[j] 为中心的最长的回文子串，其最左侧下标为 j - p[j] + 1。

以 s[j] 为中心的最长回文串在 s[l:r] 之外这一判断条件对应的逻辑运算为 j - d[j] + 1 <= l 。

字符 s[i] 到回文子串 s[l : r] 边界的距离为 r - i。

再次提醒，本题分析过程中的所有下标都在闭区间 [0, 2n] 内，所有的范围都是左闭右闭区间。

复杂度分析

时间、空间复杂度均为O(N)。

知识点

字符串，回文

代码

class Solution {
public:
    int countSubstrings(string s) {
        int n = s.size();
        string newStr = "#";
        for (char c : s) {
            newStr += c;
            newStr += "#";
        }
          s = newStr;
        vector<int> p(2 * n + 1, 0);
        for (int i = 0, l = 0, r = -1; i < 2 * n + 1; ++i) {
            int counter = 0;    // 记录p[i]
            int j = l + r - i;
            if (i > r || r == -1) {
                counter++;    // 任意位置的字符本身就是一个回文串，因此回文串数目至少是1
            } else if ((j - p[j] + 1) <= l) {
                counter = r - i;
            } else {
                counter = p[j];
            }
            while (0 <= i - counter && i + counter < 2 * n + 1 && s[i - counter] == s[i + counter]) {
                counter++;
            }
            p[i] = counter;
            if (i + counter - 1 > r) {
                l = i - counter + 1;
                r = i + counter - 1;
            }
            // cout << s.substr(i - counter + 1, i + counter) << endl;
        }
        int result = 0;
        for (int i = 0; i < 2 * n + 1; ++i) {
            result += p[i] / 2;
            // cout << p[i] / 2 << " ";
        }
        return result;
    }
};

官方代码

class Solution {
public:
    int countSubstrings(string s) {
        int n = s.size();
        string t = "$#";
        for (const char &c: s) {
            t += c;
            t += '#';
        }
        n = t.size();
        t += '!';
        auto f = vector <int> (n);
        int iMax = 0, rMax = 0, ans = 0;
        for (int i = 1; i < n; ++i) {
            // 初始化 f[i]
            f[i] = (i <= rMax) ? min(rMax - i + 1, f[2 * iMax - i]) : 1;
            // 中心拓展
            while (t[i + f[i]] == t[i - f[i]]) ++f[i];
            // 动态维护 iMax 和 rMax
            if (i + f[i] - 1 > rMax) {
                iMax = i;
                rMax = i + f[i] - 1;
            }
            // 统计答案, 当前贡献为 (f[i] - 1) / 2 上取整
            ans += (f[i] / 2);
        }
        return ans;
    }
};

Leetcode题解

647. 回文子串

647. 回文子串

题目描述

解题思路

用到的数据结构

过程描述

下标细节

复杂度分析

知识点

代码

参考资料