两者都使用扩展中心算法来寻找最长的回文子串，为什么一个更快？

Question

这是更快的解决方案A，它只能在leetcode上执行6ms，而且几乎和Manacher算法一样快（在leetcode上为6ms）。

class Solution {
public:
    string longestPalindrome(string s) {
        if (s.empty()) return "";
        if (s.size() == 1) return s;
        int min_start = 0, max_len = 1;
        for (int i = 0; i < s.size();) {
            if (s.size() - i <= max_len / 2) break;
            int j = i, k = i;
            while (k < s.size()-1 && s[k+1] == s[k]) ++k; // Skip duplicate characters.
            i = k+1;
            while (k < s.size()-1 && j > 0 && s[k + 1] == s[j - 1]) { ++k; --j; } // Expand.
            int new_len = k - j + 1;
            if (new_len > max_len) { min_start = j; max_len = new_len; }
        }
        return s.substr(min_start, max_len);
    }
};

而且我不明白为什么吹制解决方案B与解决方案A相比要慢得多，而解决方案A的运行时间为16毫秒。

class Solution {
public:
    int expandAroundCenter(string s, int left,int right) {
        int L = left, R = right;
        while(L >=0 && R < s.length() && s[L] == s[R]) {
            L--;
            R++;
        }

        return R - L - 1;
    }

    string longestPalindrome(string s) {
        int start = 0, end = 0;
        if (s.empty()) return "";
        if (s.size() == 1) return s;
        for(size_t i = 0; i < s.length(); i++) {
            int len1 = expandAroundCenter(s, i, i);
            int len2 = expandAroundCenter(s, i, i + 1);
            int len = std::max(len1, len2);
            if(len > end - start + 1) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }

            if(start + len > s.length()) break;
        }

        return s.substr(start, end - start + 1);
    }

};

由于它们都是扩展中心算法并且得到O（N ^ 2）时间复杂度和O（1）空间复杂度（Manacher算法获得O（n）时间复杂度），我只能推测编码方法是最重要的因素。好吧，如果是这样，我真的想知道原因。

通过优化，解决方案B仍然比A慢50％。

class Solution {
public:
    int expandAroundCenter(const string& s, int left,int right) {
        int L = left, R = right;
        while(L >=0 && R < s.length() && s[L] == s[R]) {
            L--;
            R++;
        }

        return R - L - 1;
    }

    string longestPalindrome(const string& s) {
        int max_len = 0;
        int min_start = 0;
        if (s.empty()) return "";
        if (s.size() == 1) return s;
        for(size_t i = 0; i < s.length(); i++) {
            if (s.size() - i <= max_len / 2) 
                break;

            int j = i, k = i;
            while (k < s.size()-1 && s[k+1] == s[k]) ++k;
            int len = expandAroundCenter(s, j, k);

            if(len > max_len) {
                max_len = len;
                min_start = j - (len - (k - j + 1)) / 2;
            }
        }

        return s.substr(min_start, max_len);
    }

};

Answer 1

算法A首先跳过抽取的字符序列，这很可能构成基准的重要部分。算法B针对该陷阱而下降并且对抽取的序列进行两次迭代，对于谓词的每次调用一次。

采用基准测试套件，用[Pad][Character][Pad]替换所有单个字符重复，然后优化中断。