5. Наибольшая палиндромная подстрока (Longest Palindromic Substring)

class Solution {
public:
    string longestPalindrome(string s) {
        
        // тривиальный случай
        if (s.size() < 2) return s;

        // формируем вспомогательную строчку нечётной длины
        // если s = abcd, то t = #a#b#c#d#
        string t(s.size() * 2 + 1, '#');
        for (int i = 0, j = 1; i < s.size(); i++, j += 2) {
            t[j] = s[i];
        }

        int c = 0; // центр текущего палиндрома
        int r = 0; // правая граница текущего полиндрома
        int best = 0; // индекс наилучшего палиндрома
        vector<int> P(t.size(), 0); // массив радиусов полиндромов для каждого индекса

        // проход по строке, определение наилучшего палиндрома
        for (int i = 0; i < t.size(); i++) {

            // если индекс внутри границы текущего палиндрома,
            // оценим минимально возможный радиус для индекса
            // это наименьшая величина между зеркалом и r-i
            if (i < r) {
                P[i] = min(P[2*c - i], r - i);
            }

            // определение радиуса
            int a = i - P[i] - 1, b = i + P[i] + 1;
            while (a >= 0 && b < t.size() && t[a] == t[b]) {
                P[i]++;
                a--;
                b++;
            }

            // если палиндром расширяется, определяем новый центр и границу
            if (i + P[i] > r) {
                c = i;
                r = c + P[i] - 1;

                if (P[i] > P[best]) {
                    best = i;
                }
            }
        }

        return s.substr(best/2 - P[best] / 2, P[best]);
    }
};