#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)/2;
    return s1.substr(start,maxlen);
}
int main(){
     string s = "abcbcabccbad";
     cout<<longestpalindrome(s);
     return 0;
 }