Submission details
Task:Longest palindrome
Sender:aalto26iw_001
Submission time:2026-11-04 17:16:20 +0200
Language:C++ (C++20)
Status:READY
Result:
Test results
testverdicttime
#1ACCEPTED0.00 sdetails
#2ACCEPTED0.00 sdetails
#3--details
#4--details
#5--details
#6--details
#7--details
#8--details
#9ACCEPTED0.00 sdetails
#10ACCEPTED0.00 sdetails
#11--details
#12ACCEPTED0.00 sdetails
#13ACCEPTED0.00 sdetails
#14ACCEPTED0.00 sdetails
#15ACCEPTED0.00 sdetails
#16--details

Compiler report

input/code.cpp: In function 'std::string longestPalindrome(std::string, std::string)':
input/code.cpp:116:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |     while (center < r.length())
      |            ~~~~~~~^~~~~~~~~~~~
input/code.cpp:118:68: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |         while (center - (radius + 1) >= 0 && center + (radius + 1) < r.length() && r[center - (radius + 1)] == r[center + (radius + 1)])
      |                                              ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
input/code.cpp:151:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  151 |     for (int i = 0; i < palindromeLengt...

Code

#include <bits/stdc++.h>
typedef long long ll;

using namespace std;
class Manacher {
public: 

    // p[i] = radius of longest palindrome centered at i 
    // in transformed string
    vector<int> p;    
    
    // transformed string with # and sentinels
    string ms;        

    // preprocess the string and run the algorithm
    Manacher(string &s) {
        
        // left sentinel
        ms = "@"; 
        for (char c : s) {
            ms += "#" + string(1, c);
        }
        
        // right sentinel
        ms += "#$"; 

        // run Manacher’s algorithm
        runManacher();
    }

    void runManacher() {
        int n = ms.size();
        p.assign(n, 0);
        int l = 0, r = 0;

        for (int i = 1; i < n - 1; ++i) {
            
            // mirror of i around center (l + r)/2
            int mirror = l + r - i;

            // initialize p[i] based on its mirror 
            // if within bounds
            if (i < r)
                p[i] = min(r - i, p[mirror]);

            // expand palindrome centered at i
            while (ms[i + 1 + p[i]] == ms[i - 1 - p[i]]){
                ++p[i];
            }

            // update [l, r] if the palindrome expands 
            // beyond current r
            if (i + p[i] > r) {
                l = i - p[i];
                r = i + p[i];
            }
        }
    }

    // returns length of longest palindrome centered 
    // at 'cen' in original string
    // 'odd' = 1 → check for odd-length, 'odd' = 0 → even-length
    int getLongest(int cen, int odd) {
        
        // map original index to transformed string index
        int pos = 2 * cen + 2 + !odd;
        return p[pos];
    }

    // checks if s[l..r] is a palindrome in O(1)
    bool check(int l, int r) {
        int len = r - l + 1;
        int cen = (l + r) / 2;
        return len <= getLongest(cen, len % 2);
    }
};

string longestPalindrome(string s) {
        Manacher mob(s);
        int n = s.size();
        
        // maximum length found so far
        int maxLen = 1;     
        
        // starting index of longest palindrome
        int bestStart = 0;  

        for (int i = 0; i < n; i++) {
            
            // check for odd-length palindrome centered at i
            int oddLen = mob.getLongest(i, 1);
            if (oddLen > maxLen) {
                maxLen = oddLen;
                bestStart = i - maxLen / 2;
            }

            // check for even-length palindrome centered 
            // between i and i+1
            int evenLen = mob.getLongest(i, 0);
            if (evenLen > maxLen) {
                maxLen = evenLen;
                bestStart = i - maxLen / 2 + 1;
            }
        }

        // extract the longest palindromic substring
        return s.substr(bestStart, maxLen);
}

string longestPalindrome(string s, string r)
{
    vector<int> palindromeLengths(r.length(), 0);

    int center = 0;
    int radius = 0;
    while (center < r.length())
    {
        while (center - (radius + 1) >= 0 && center + (radius + 1) < r.length() && r[center - (radius + 1)] == r[center + (radius + 1)])
        {
            radius++;
        }
        palindromeLengths[center] = radius;
        int oldCenter = center;
        int oldRadius = radius;
        center++;
        radius = 0;
        while (center <= oldCenter + oldRadius)
        {
            int mirroredCenter = oldCenter - (center - oldCenter);
            int maxMirroredRadius = oldCenter + oldRadius - center;

            if (palindromeLengths[mirroredCenter] < maxMirroredRadius)
            {
                palindromeLengths[center] = palindromeLengths[mirroredCenter];
                center++;
            }
            else if (palindromeLengths[mirroredCenter] > maxMirroredRadius)
            {
                palindromeLengths[center] = maxMirroredRadius;
                center++;
            }
            else
            {
                radius = maxMirroredRadius;
                break;
            }
        }
    }
    int maxCenter = 0;
    int maxLength = 0;
    for (int i = 0; i < palindromeLengths.size(); i++)
    {
        if (palindromeLengths[i] > maxLength)
        {
            maxLength = palindromeLengths[i];
            maxCenter = i;
        }
    }
    string result;
    for (int i = (maxCenter) - (maxLength); i < maxCenter + maxLength; i++)
    {
        if (r[i] != '#')
        {
            result += r[i];
        }
    }
    return result;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    string s, t;
    cin >> s;
    string r = "#";
    for (int i = 0; i < s.size(); i++)
    {
        r = r + s[i] + '#';
    }
    cout << longestPalindrome(s) << endl;
}

Test details

Test 1

Verdict: ACCEPTED

input
aaaaaaaaaa

correct output
aaaaaaaaaa

user output
aaaaaaaaaa

Test 2

Verdict: ACCEPTED

input
ababababab

correct output
ababababa

user output
ababababa

Test 3

Verdict:

input
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

correct output
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

user output
(empty)

Test 4

Verdict:

input
ababababababababababababababab...

correct output
ababababababababababababababab...

user output
(empty)

Test 5

Verdict:

input
aztdvxzjwxtrludymvpradgbdpgnrq...

correct output
aztdvxzjwxtrludymvpradgbdpgnrq...

user output
(empty)

Test 6

Verdict:

input
vvfigwwsyxbukedgcfyibvtbclybud...

correct output
vvfigwwsyxbukedgcfyibvtbclybud...

user output
(empty)

Test 7

Verdict:

input
abaabaaaaaaabaababbbbbbabaaabb...

correct output
babbbabbbaabbbbaabbbbbbbbaabbb...

user output
(empty)

Test 8

Verdict:

input
txolestmgyepwrpofxyesjtsfkhjac...

correct output
yxnbaabnxy

user output
(empty)

Test 9

Verdict: ACCEPTED

input
ihpohpzoffel

correct output
ff

user output
ff

Test 10

Verdict: ACCEPTED

input
flexflexvpqxierullgcfckjqflexf...

correct output
cfc

user output
cfc

Test 11

Verdict:

input
aabbabaabbaababbabaababbaabbab...

correct output
abaababbaabbabaababbabaabbaaba...

user output
(empty)

Test 12

Verdict: ACCEPTED

input
obsession

correct output
ses

user output
ses

Test 13

Verdict: ACCEPTED

input
abcxcbaxcba

correct output
abcxcba

user output
abcxcba

Test 14

Verdict: ACCEPTED

input
zzabc

correct output
zz

user output
zz

Test 15

Verdict: ACCEPTED

input
aaccaabbaaccaaccaabbaaccaa

correct output
aaccaabbaaccaaccaabbaaccaa

user output
aaccaabbaaccaaccaabbaaccaa

Test 16

Verdict:

input
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

correct output
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

user output
(empty)