C++ O(n) solution { Using Manacher's Algorithm }


#1

// MANACHER’S ALGORITHM { TC: O(N) }
string convertToNewString(const string &s)
{
string newString = “@”;

for(int i=0;i<s.size();i++) 
{
    newString += '#';
    newString += s[i];
}

newString += "#$";
return newString;

}

string Solution::longestPalindrome(string s)
{
string Q = convertToNewString(s);
vector P(Q.size());
int c = 0, r = 0; // current center, right limit

for(int i=1;i<Q.size()-1;i++) 
{
    //corresponding mirror letter
    int iMirror = c - (i - c);

    if(i<r) 
    {
        P[i] = min(r-i,P[iMirror]); // IMP STEP
    }

    // expanding around center i
    while(Q[i+(1+P[i])] == Q[i-(1+P[i])])
    {
        P[i]++;
    }

    // Update c,r in case if the palindrome centered at i expands past r,
    if(i+P[i] > r) 
    {
        c = i; // next center = i
        r = i + P[i]; // next right limit
    }
}

// For the longest palindrome.

int maxPalindrome = 0;
int centerIndex = 0;

for(int i=1;i<Q.size()-1;i++) 
{
    if(P[i] > maxPalindrome) 
    {
        maxPalindrome = P[i];
        centerIndex = i;
    }
}

// left limit of max palindrome subarray will be staring index;
int startIndex = (centerIndex-maxPalindrome-1)/2; 

return s.substr(startIndex, maxPalindrome);

}