欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

回文三板斧(第三招:发掘马拉车的剩余价值)

程序员文章站 2022-09-17 08:18:58
有些题目需要频繁的判断任意子串是否是回文的。本文分享一下利用马拉车的长度数组判断任意子串是否回文的方法,时间复杂度低至 O(1) 。先来回忆一下马拉车:选择占位符,根据原始字符串 S 构造字符串 PS。O(n) 的计算长度数组 len。len[i] 表示 PS 中,以 PS[i]为中心的最长的回文子串的长度。当我们要判断 S[L:R]是否为回文串时,仅需两个步骤:找到 PS 中与 S[L:R] 对应的子串位置,记为 PS[L’: R’]。L’ = L*2+1R’ = R*2+1...

有些题目需要频繁的判断任意子串是否是回文的。本文分享一下利用马拉车的长度数组判断任意子串是否回文的方法,时间复杂度低至 O(1) 。
回文三板斧(第三招:发掘马拉车的剩余价值)
先来回忆一下马拉车:

  • 选择占位符,根据原始字符串 S 构造字符串 PS。
  • O(n) 的计算长度数组 len。len[i] 表示 PS 中,以 PS[i]为中心的最长的回文子串的长度。

当我们要判断 S[L:R]是否为回文串时,仅需两个步骤:

  • 找到 PS 中与 S[L:R] 对应的子串位置,记为 PS[L’: R’]。
    • L’ = L*2+1
    • R’ = R*2+1
  • 判断 len[mid] 是否小于PS[L’:R’]的长度。如果小于,则S[L:R]不是回文,反之则是。
    • mid = (L’ + R’) / 2

回文三板斧(第三招:发掘马拉车的剩余价值)

以 S[1:5] 为例,首选换算对应子串位置,得到 PS[3:11],找到PS[3:11]的中心 PS[7],通过查询长度数组 len,得知以 PS[7] 为中心的最长回文串的长度为 15。显然 PS[3:11] 及 S[1:5] 都是回文的。
偶数长度的字符串同样有效,比如 S[6:7],老铁们可自行验证~

尝试证明一下

因为 len[mid] 记录的是以 PS[mid] 为中心最长回文子串的长度。而S[L:R] 对应的PS[L’:R’] 也是以 PS[mid] 为中心的子串。显然:

  • 当 PS[L’:R’] 的长度不超过 len[i] 时,PS[L’:R’] 一定是回文串。
  • 当 PS[L’:R’] 超过 len[mid],PS[L’ : R’] 一定不是回文串。

否则的话就与长度数组 len 的定义矛盾了,所以上述结论一定是成立的。

几个练习题

代码

class Manacher {
    public:
    Manacher(const std::string &s) {
        construct(s);
    };

    // s[L:R] 是否是回文的
    bool isPalindrome(int L, int R) {
        L = L*2 + 1;
        R = R*2 + 1;
        int mid = (L+R)/2;
        if(0 <= mid && mid < len.size() && R-L+1 <= len[mid]) {
            return true;
        }
        return false;
    }

    private:
    vector<int> len;

    void construct(const std::string &s) {
        vector<char> vec;
        // 用 0 作为分隔符
        vec.resize(s.size()*2+1);
        for(int i = 0; i < s.size(); i++) {
            vec[i<<1|1] = s[i];
        }

        int L = 0, R = -1;
        len.resize(vec.size());
        
        for(int i = 0, n = vec.size(); i < n; i++) {
            if(i <= R) {
                len[i] = min((R-i)*2+1, len[L+R-i]);
            } else {
                len[i] = 1;
            }
            int l = i - len[i]/2 - 1;
            int r = i + len[i]/2 + 1;
            while(0 <= l && r < vec.size() && vec[l] == vec[r]) {
                --l;
                ++r;
            }
            len[i] = r-l-1;
            if(r > R) {
                L = l+1;
                R = r-1;
            }
        }
    }
};

回文三板斧(第三招:发掘马拉车的剩余价值)

本文地址:https://blog.csdn.net/Time_Limit/article/details/107899463

相关标签: --- 回文 ---