dsa-competitive-programming/leetcode/lc5/manachers.cpp

class Solution{
    public:
        string LongestPalindrome(string s){
            if(s.empty()) return "";
            string t = "#";
            for(char c : s){
                t+=c;
                t+="#";
            }
            int n = t.size();
            vector<int> p(n,0);
            int C =0;
            int R =0;

            for(int i=0;i<n;i++){
                int mirror = 2*C-i;

                if(i<R){
                    p[i] = min(R-i, p[mirror]);
                }
                while(i+p[i]+1<n && i-p[i]-1>=0 && t[i+p[i]+1] == t[i-p[i]-1]){
                            p[i]++;
                }
                if(i+p[i]>R){
                C = i;
                R = i+p[i];
                }

            }
            int maxLen = 0;
            int centerIndex = 0;
            for(int i =0;i<n;i++){
                if(p[i]>maxLen){
                    maxLen = p[i];
                    centerIndex = i;
                }
            }
            int start = (centerIndex-maxLen)/2;
            return s.substr(start, maxLen);
        }
}