#include <iostream>
#include<vector>
using namespace std;
string updatedString(string s){
    string newStr ="^";
    for(int i=0;i<s.size();i++){
        newStr += "#";
        newStr += s[i];
    }
    newStr += "#$";
    return newStr;
}
string longestPalindrome(string s1){
    string s = updatedString(s1);
    int n = s.size();
    vector<int> L(n,0);
    int center = 0;
    int right = 0;
    for(int i=1;i<n-1;i++){
        int mirror = 2 * center * i;
        if(right>i){
            L[i] = min(right-i,L[mirror]);
        }else{
            L[i]=0;
        }
        while(s[i+1+L[i]] == s[i-1-L[i]]){
            L[i]++;
        }
        if(i+L[i]>right){
            center = i;
            right = i+L[i];
        }
    }
    int maxLen=0,int maxCenter=0;
    for(int i=1;i<n-1;i++){
        if(L[i]>maxLen){
            maxLen=L[i];
            maxCenter = i;
        }
    }
    int start = (maxCenter - maxLen);
    return s.substr(start,maxLen);
}
int main() {
    string s="abcbcabcbad";
    cout<<longestPalindrome(s);
    return 0;
}