最长回文子串问题 - O(N^2 logN) 解决方案 - 二分查找

Question

最长回文子串问题：
给定一个字符串s，returns中最长的回文子串
例如。

Input: s = "babad"
Output: "bab"
Note: "aba" is also a valid answer.

问题
下面的代码是Errichto（codeforces的一个RedCoder）的解决方案。这是对同一问题的 O(N^3) 解决方案的改进。在他的 youtube 频道上，他一步一步地逐步更有效地解决问题。但是我很难理解他对这个解决方案的方法。我的问题是：

在good函数中，L + x <= n条件有什么用
在做二分查找之前，好像做了一些与奇偶校验相关的事情。为什么？它对解决方案有何贡献？
这里的二分查找有点奇怪。我了解基本的二进制搜索，但没有得到这个变体。谁能给我解释一下？

代码

bool is_palindrome(string s) {
    string rev = s;
    reverse(rev.begin(), rev.end());
    return s == rev;
}
// returns true if there is a palindrome of length x
int good(int x, string s) {
    int n = s.length();
    for(int L = 0; L + x <= n; L++) {
        if(is_palindrome(s.substr(L, x))) {
            return L;
        }
    }
    return -1;
}
class Solution {
public:
    string longestPalindrome(string s) {
        int best_len = 0;
        string best_s = "";
        int n = s.length();
        for(int parity : {0, 1}) {
            int low = 1, high = n;
            if(low % 2 != parity) low++;
            if(high % 2 != parity) high--;
            while(low <= high) {
                int mid = (low + high) / 2;
                if(mid % 2 != parity) {
                    mid++;
                }
                if(mid > high) {
                    break;
                }
                int tmp = good(mid, s);
                if(tmp != -1) {
                    if(mid > best_len) {
                        best_len = mid;
                        best_s = s.substr(tmp, mid);
                    }
                    low = mid + 2;
                }
                else {
                    high = mid - 2;
                }
            }
        }
        return best_s;
    }
};

Answer 1

In the 'good' function below why the condition in the for loop is L+x<=n.

因为正如您在评论中提到的：

// returns true if there is a palindrome of length x

我们关注的是子字符串 [L,L+x)。例如。第一次迭代：[0,x-1]，第二次迭代：[1,(x-1)+1] 等等，直到 [n-x,n-1]。因此 L 一直到 n-x.

Answer 2

bool is_palindrome(string s) {
string rev = s;
reverse(rev.begin(), rev.end());
return s == rev;
}

这会复制字符串，反转该副本，然后将反转的内容与原始内容进行比较。不言自明但值得注意的是，c++ 具有反向迭代器，因此您可以执行 equal(rev.begin(), rev.end(), rev.rbegin())，它将从头开始的每个元素与从头开始的每个元素进行比较，而无需复制。一旦发现不匹配的字符，它也会足够聪明地退出。

int good(int x, string s) {
int n = s.length();
for(int L = 0; L + x <= n; L++) {
    if(is_palindrome(s.substr(L, x))) {
        return L;
    }
}
return -1;
}

这是检查长度为 x 的 s 的任何可能子串是否为回文串。 substr 获取起始字符的索引和从那里开始的字符数以获取其子字符串。因此，例如如果 s = "myString" 那么 substr(1, 3) 将给出 "ySt"，从索引 1 开始的 3 个字符。如果起始位置加上字符数大于字符串的长度，您已经结束了，这就是如果 L + x > n.

它终止的原因

至于解决方案class……恶心。想象一下，搜索 space 是一个可能长度的数组：1, 2, 3, 4, 5, 6, 7 ...n，其中 n 是字符串的长度。对于它测试的每个长度，它将检查该长度的每个可能的子串，看是否有一个是回文串。如果有的话，它将检查可能长度数组的中点高于该测试长度，否则低于该长度。

二分查找的具体代码比较难读懂，想看懂的可以去geekforgeeks或者rosetta code上找更好的自己实现。

理解逻辑的关键点是它与对不同可能长度的数组进行二进制搜索相同。

最长回文子串问题 - O(N^2 logN) 解决方案 - 二分查找

Longest Palindromic Substring Problem - O(N^2 logN) Solution - Binary search

c++

c++11

binary-search

longest-substring