5. 最长回文子串

gistfile1.txt

string longestPalindrome(string s) {
    int n = s.size(), jT = 0, kT = 0, maxL = 0;
    for (int i = 0; i < n; ++i) {
        int j = i, k = i;
        while (j >= 0 && k < n) {
            if (s[j] == s[k]) {
                j--;
                k++;
            }
            else {
                break;
            }
        }
        if (j + 1 != k - 1 && k - j + 1 > maxL) {
            jT = j + 1;
            kT = k - 1;
            maxL = k - j + 1;
        }
        j = i, k = i + 1;
        while (j >= 0 & k < n) {
            if (s[j] == s[k]) {
                j--;
                k++;
            }
            else {
                break;
            }
        }
        if (j != k - 1 && k - j + 1 > maxL) {
            jT = j + 1;
            kT = k - 1;
            maxL = k - j + 1;
        }
    }
    return s.substr(jT, kT - jT + 1);
}

记录下已经知的最大长度，之后小于等于这个长度的都跳过

嗯，不算是剪枝，O(∩_∩)O~