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

sol.cc

void calc(vector<int> &d1, vector<int> &d2, const string &s, int n) {
    for (int i = 0, l = 0, r = -1; i < n; i++) {
        int k = (i > r) ? 1 : min(d1[l + r - i], r - i + 1);
        while (0 <= i - k && i + k < n && s[i - k] == s[i + k]) {
            k++;
        }
        d1[i] = k--;
        if (i + k > r) {
            l = i - k;
            r = i + k;
        }
    }
    
    for (int i = 0, l = 0, r = -1; i < n; i++) {
        int k = (i > r) ? 0 : min(d2[l + r - i + 1], r - i + 1);
        while (0 <= i - k - 1 && i + k < n && s[i - k - 1] == s[i + k]) {
            k++;
        }
        d2[i] = k--;
        if (i + k > r) {
            l = i - k - 1;
            r = i + k ;
        }
    }
}

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        if(n == 0) return "";
        vector<int> d1(n, 0), d2(n, 0);
        calc(d1, d2, s, n);
        int odd_index = distance(begin(d1), max_element(begin(d1), end(d1)));
        int even_index = distance(begin(d2), max_element(begin(d2), end(d2)));
        int odd_value = d1[odd_index], even_value = d2[even_index];
        if(odd_value > even_value) {
            return s.substr(odd_index - odd_value + 1, 2 * odd_value - 1);
        } else {
            return s.substr(even_index - even_value, 2 * even_value);
        }
    }
};