5. Longest Palindromic Substring

manacher’s algorithm可以O(n)但是不会
O(n²)

class Solution:
    def longestPalindrome(self, s: str) -> str:
        def find(l, r):
            while 0 <= l and r < len(s) and s[l] == s[r]:
                l -= 1
                r += 1
            return l + 1, r - 1
        ll, rr = 0, 0
        for i in range(len(s)):
            l, r = find(i, i)
            if r - l > rr - ll: ll, rr = l, r
            l, r = find(i, i + 1)
            if r - l > rr - ll: ll, rr = l, r
        return s[ll:rr + 1]

class Solution:
    def longestPalindrome(self, s: str) -> str:
        ll, rr = 0, 0
        for i in range(len(s)):
            l, r = self.find(s, i, i)
            if r - l > rr - ll: ll, rr = l, r
            l, r = self.find(s, i, i + 1)
            if r - l > rr - ll: ll, rr = l, r
        return s[ll:rr + 1]

    def find(self, s, l, r):
        while 0 <= l and r < len(s) and s[l] == s[r]:
            l -= 1
            r += 1
        return l + 1, r - 1

class Solution {
public:
    string longestPalindrome(string s) {
        int ll = 0, rr = 0;
        auto search = [&s, &ll, &rr](int l, int r) {
            while (0 <= r && r < size(s) && s[l] == s[r]) {
                --l;
                ++r;
            }
            if (r - l > rr - ll) {
                ll = l;
                rr = r;
            }
        };
        for (int i = 0; i < size(s); ++i) {
            search(i, i);
            search(i, i + 1);
        }
        return s.substr(ll + 1, rr - ll - 1);
    }
};

因为回文串是对称的，所以枚举所有可能的对称轴
对称轴可能是某个字符，也可能是两个字符中间，填充#符号来避免奇偶问题
枚举每个可能的对称轴，从对称轴开始向左右两边比较字符直到找到不一样的或者越界，然后左右指针均回退一个（回退以后一定都是指向#符号），更新全局左右指针
最后重建原字符串里的最长回文子字符串
O(n²)

class Solution:
    def longestPalindrome(self, s: str) -> str:
        s = '#' + '#'.join(list(s)) + '#'
        n = len(s)
        ll, rr = n, n
        for i in range(1, n):
            l, r = i - 1, i + 1
            while 0 <= l and r < n and s[l] == s[r]:
                l -= 1
                r += 1
            if r - l > rr - ll: ll, rr = l + 1, r - 1
        return s[ll + 1 : rr : 2]

class Solution {
public:
    string longestPalindrome(string s) {
        string str = "#";
        for (char c : s) {
            str += c;
            str += '#';
        }
        int n = str.length(), ll = 0, rr = 0;
        for (int i = 1; i < n - 1; ++i) {
            int l = i - 1, r = i + 1;
            while (0 <= l && r < n && str[l] == str[r]) {
                --l;
                ++r;
            }
            ++l;
            --r;
            if (r - l > rr - ll) {
                ll = l;
                rr = r;
            }
        }
        string res;
        for (int i = ll + 1; i <= rr; i += 2) {
            res += str[i];
        }
        return res;
    }
};

class Solution {
public:
    string longestPalindrome(string s) {
        string str = split(s);
        int n = str.length();
        int left = 0, right = 0;
        for (int i = 1; i < n - 1; ++i) {
            int l = i, r = i;
            while (str[l] == str[r] && l >= 0 && r < n) {
                --l;
                ++r;
            }
            ++l;
            --r;
            if (r - l > right - left) {
                left = l;
                right = r;
            }
        }
        return reconstruct(str, left, right);
    }

    string split(string &s) {
        string str = "#";
        for (const auto &c : s) {
            str += c;
            str += '#';
        }
        return str;
    }

    string reconstruct(string &s, int l, int r) {
        string str;
        for (int i = l + 1; i < r; i += 2) {
            str += s[i];
        }
        return str;
    }
};

memo+recursive
f(l, r)表示s[l:r]中最长的回文串的长度

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.length(), b = 0;
        m.resize(n, vector<int>(n, -1));
        int mx = f(s, 0, n - 1);
        for (int l = 0, r = l + mx - 1; 0 <= r && r < n; ++l, ++r) {
            if (m[l][r] == mx) return s.substr(l, mx);
        }
        return "";
    }

    int f(const string &s, int l, int r) {
        if (l > r) return 0;
        if (m[l][r] > 0) return m[l][r];
        if (l == r) return m[l][r] = 1;
        m[l][r] = max(f(s, l, r - 1), f(s, l + 1, r));
        if (s[l] == s[r]) {
            int t = f(s, l + 1, r - 1);
            if (l + t + 1 == r) {
                m[l][r] = max(m[l][r], r + 1 - l);
            }
        }
        return m[l][r];
    }

    vector<vector<int>> m;
};