如何在c ++中使用二进制搜索来解决最长回文子字符串的问题？请解释以下代码

Question

最长回文子串

输入：“ babad”输出：“ bab”注意：“ aba”也是有效答案。

[如果您能逐行解释代码，那就太好了。]在下面的“良好”函数中，为什么for循环中的条件为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

在下面的“好”函数中，为什么for循环中的条件为L + x <= n。

因为您在评论中已经提到：

//如果回文长度为x，则返回true

我们关注子字符串[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）将给出从索引1开始的3个字符“ ySt”。如果起始位置加上字符数大于字符串的长度，则表示结束，这就是为什么如果L + x> n会终止的原因。

关于解决方案类...可以想象，搜索空间是一个可能的长度数组：1、2、3、4、5、6、7 ... n，其中n是字符串的长度。对于它测试的每个长度，它将检查该长度的每个可能的子串，以查看是否是回文。如果有，它将检查可能长度超过该测试长度的数组的中点，否则检查下面的那个。

二进制搜索的实际代码很难具体阅读和理解，如果您想了解它，可以在geekforgeeks或rosetta代码上找到更好的代码，以便自己实现。

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