longest_palindromic_substring.cc

// https://leetcode.com/problems/longest-palindromic-substring

class Solution {
public:
    string longestPalindrome(const string &s) { // Manacher's algorithm, O(n) time
        if (s.size() <= 1) return s;

        // insert a bogus char between chars, including outer boundaries
        string t = "|";
        for (auto ch : s) t += ch, t += "|";
        int n = t.size();

        // dp[i] is the radius of the longest palindromic substring centered at t[i]
        vector<int> dp(n);
        int center = 0, bCur = 0;

        for (int i = 0; i < n; i++) {
            dp[i] = bCur <= i ? 0 : min(bCur - i, dp[center - (i - center)]);

            int start = i - dp[i], end = i + dp[i];

            while (start - 1 >= 0 && end + 1 < n && t[start - 1] == t[end + 1]) {
                --start;
                ++end;
                ++dp[i];
            }

            if (i + dp[i] > bCur) {
                bCur = i + dp[i];
                center = i;
            }
        }

        center = max_element(begin(dp), end(dp)) - begin(dp);

        return s.substr((center - dp[center])/2, dp[center]);
    }
};