频繁查询子串是否回文：Manacher预处理后$O(1)$响应

摘要: Manacher 预处理信息的应用

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

在回文的场景中，我们经常会遇到在一个字符串 $s$ 上频繁地给定一个区间 $[i, j]$，问该子串 $s[i..j]$ 是否是回文。

此时可以通过区间 DP 预处理一个二维数组 $p[i][j]$ 表示子串 $s[i..j]$ 是否是回文。这样可以在 $O(N^{2})$ 的时间完成预处理，在 $O(1)$ 的时间响应每次查询。

我们还知道解决最长回文子串问题的 Manacher 算法，它也是一个先预处理再响应查询的过程，如果将 Manacher 算法的预处理的中间结果善加利用，则可以对上述区间 DP 的方案进行改进。

Manacher 中的信息

在文章 Manacher算法：基于对称性的优化，信息论直觉 中，我们了解了 Manacher 算法。

当我们进行完 Manacher 的预处理时，得到数组 $p[i]$ 表示在给原串 $S$ 插入特殊字符后的串 $T$ 上，以 $T[i]$ 为中心的回文子串的半径。

当给定 $S$ 的子串 s[i..j]，问 s[i..j] 是否是回文子串时，仅需以下两步：

step1：找到 s[i..j] 在 $T$ 中的对应位置，即 T[2i+1..2j+1]。

step2：对应在 $T$ 上的子串 T[2i+1..2j+1] 的中点为 $m = \frac{2i+1 + 2j+1}{2} = i + j + 1$。判断 $p[m]$ 是否小于子串的长度 $(2j+1) - (2i+1) + 1 = 2j-2i+1$，如果是，则不是回文子串，如果否，则是回文子串。

131. 分割回文串

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串。返回 s 所有可能的分割方案。

示例 1：
输入：s = “aab”
输出：[[“a”,”a”,”b”],[“aa”,”b”]]

示例 2：
输入：s = “a”
输出：[[“a”]]

提示：

1 <= s.length <= 16
s 仅由小写英文字母组成

算法：回溯

从 $i=0$ 出发，取一个以 i 开头的回文子串 $s[i..j]$，其中 $i \leq j < n$，然后继续取下一个回文子串，直至 $s$ 耗尽。

在 $i$ 位置时，以 $i$ 开头的回文子串可能有很多个，以 DFS 的方式一个一个地取，构造答案即可。

具体做法是，枚举 j = i, i+1, ..., n-1，判定子串 s[i..j] 是否是回文串，若是，则将该子串压入当前答案序列，回溯后再弹出。

在判定 [i, j] 是否是回文时，直接线性扫描即可。

代码(C++)

class Solution {
public:
    vector<vector<string>> partition(string s) {
        if(s.empty()) 
            return vector<vector<string> >();
        int n = s.size();
        if(n == 1) 
            return vector<vector<string>>{{s}};
        vector<vector<int> > is_palindrome(n, vector<int>(n, -1)); // dp
        vector<vector<string> > result;
        vector<string> path;
        dfs(s, 0, is_palindrome, path, result);
        return result;
    }

private:
    void dfs(const string& s, int i, vector<vector<int> >& is_palindrome,
            vector<string>& path, vector<vector<string> >& result)
    {
        int n = s.size();
        if(i >= n)
        {
            result.push_back(path);
            return;
        }

        for(int j = i; j < n; ++j)
        {
            if(!_check(s, i, j, is_palindrome)) 
                continue;
            path.push_back(s.substr(i, j - i + 1));
            dfs(s, j + 1, is_palindrome, path, result);
            path.pop_back();
        }
    }

    bool _check(const string& s, int left, int right, vector<vector<int> >& is_palindrome)
    {
        if(is_palindrome[left][right] != -1)
            return is_palindrome[left][right] == 1;
        while(left < right)
        {
            if(s[left] == s[right])
            {
                ++left;
                --right;
            }
            else
            {
                is_palindrome[left][right] = 0;
                return false;
            }
        }
        is_palindrome[left][right] = 1;
        return true;
    }
};

优化：Manacher 预处理

可以把 s[i..j] 是否是回文串的信息预处理出来，比如动态规划的方式，可以 $O(N^{2})$ 预处理完。此后就可以 $O(1)$ 查询子串是否是回文。

也可以先用 Manacher 以 $O(n)$ 预处理出 p 数组，此后根据 p 数组即可 $O(1)$ 响应查询。

这样整体算法框架还是回溯，只是在选择下一步时，判断当前步取到的子串是否回文时，可以 $O(1)$ 响应。

代码 (C++)

class Solution {
public:
    vector<vector<string>> partition(string s) {
        if(s.empty()) 
            return vector<vector<string> >();
        int n = s.size();
        if(n == 1) 
            return vector<vector<string>>{{s}};

        string t(n * 2 + 1, '#');

        for(int i = 0; i < n; ++i)
            t[2 * i + 1] = s[i];

        int m = t.size();
        vector<int> p(m, 1);
        int r = 0, c = 0;
        for(int i = 0; i < m; ++i)
        {
            int j = c * 2 - i;
            // 将不用扩展对比的部分直接置进 p[i] 中
            if(r > i)
            {
                p[i] = min(p[j], r - i);
            }
            while(i - p[i] >= 0 && i + p[i] < m && t[i - p[i]] == t[i + p[i]])
                p[i]++;
            if(i + p[i] > r)
            {
                r = i + p[i];
                c = i;
            }
        }

        vector<vector<string> > result;
        vector<string> path;
        dfs(s, 0, p, path, result);
        return result;
    }

private:
    void dfs(const string& s, int i, vector<int>& p,
            vector<string>& path, vector<vector<string> >& result)
    {
        int n = s.size();
        if(i >= n)
        {
            result.push_back(path);
            return;
        }

        for(int j = i; j < n; ++j)
        {
            if(!_check(i, j, p)) 
                continue;
            path.push_back(s.substr(i, j - i + 1));
            dfs(s, j + 1, p, path, result);
            path.pop_back();
        }
    }

    bool _check(int i, int j, vector<int>& p)
    {
        int m = i + j + 1;
        return p[m] >= j - i + 1;
    }
};

---