std::pair<std::string, std::vector<int>> manacher(const std::string_view S) {
    std::string s = "^|";
    s.reserve(S.size() * 2 + 3);
    for (auto c : S) s.push_back(c), s.push_back('|');
    s.push_back('$');
    std::vector<int> p(s.size());  //  p[i] is the radius of the longest palindrome centered at i
    for (int r = 0, mid = 0, i = 1; i < int(s.size()) - 1; ++i) {
        p[i] = r >= i ? std::min(p[mid * 2 - i], r - i) : 1;
        while (s[i - p[i]] == s[i + p[i]]) ++p[i];
        if (i + p[i] - 1 > r) r = i + p[i] - 1, mid = i;
    }
    return {std::move(s), std::move(p)};
}

std::string longest_palindromic_substring(const std::string_view S) {
    auto [s, p] = manacher(S);
    int mid = std::max_element(p.begin() + 2, p.end() - 2) - p.begin();
    std::string res(p[mid] - 1, '\0');
    for (int i = mid - p[mid] + 2, j = 0; i < mid + p[mid]; i += 2) res[j++] = s[i];
    return res;
}