Longest Palindromic Substring in Linear Time

Longest Palindromic Substring in Linear Time

Longest Palindromic Substring in Linear Time

Given a string, find the longest substring which is palindrome in Linear time O(N).

For each test case print the Longest Palindromic Substring. If there are multiple such substrings of same length, print the one which appears first in the input string.

For Input:
5
mqxqqx
abc
abcbabc
babcbabcbaccba
forgeeksskeegfor
Your Output is:
xqqx
a
abcba
abcbabcba
geeksskeeg

// { Driver Code Starts
// driver code

#include<bits/stdc++.h>
using namespace std;

string LongestPalindromeSubString(string text);

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        string s;
        cin>>s;
        cout<< LongestPalindromeSubString(s) << endl;
    }
    return 1;
}
// } Driver Code Ends


// return the longest palindrome substring
string LongestPalindromeSubString(string text)
{
    // code here

    string s="";
    int index=0;
  
  for(int i=0;i<(2*text.size()+1);++i)
  {
      if(i%2!=0)
      s+=text[index++];
      else
      s+=('$');
  }
   int n=2*text.size()+1;
   int start=0,end=0;
   int len[n];
   int x=0,y=0;
   int mx=INT_MIN;
   int i=0;
   memset(len,0,sizeof(len));
   while(i<n)
   {
  //expand around i as to find longest palindrome
       while(start>0&&(end<n-1)&&(s[start-1]==s[end+1]))
       {
          start--;
           end++;
       }
      
//set the longest value of palindrome around center i at len[i]     
len[i]=end-start+1;
      
        if((len[i]/2)>mx)
        {
            mx=len[i]/2;
            x=start,y=end;
        }
 //Current palindrome is proper suffix of input. No need to proceed. Just break out //of loop     
       if(end==n-1)
          break;
         
       int newcenter;
       if(i%2==0)
       newcenter=end+1;
       else
       newcenter=end;
      
       for(int j=i+1;j<=end;++j)
       {
//i - (j - i) is left mirror. Its possible left mirror might go beyond current center //palindrome. So take minimum of either left side palindrome or distance  j to end.
           len[j]=min(len[i-(j-i)],2*(end-j)+1);
//As soon as we find a center lets break out of this inner while loop.
           if(j+len[i-(j-i)]/2==end)
           {
               newcenter=j;
               break;
           }
          
       }
 //make i as newCenter. Set right and left to atleast the value we already know //should be matching based of left side palindrome     
       i=newcenter;
       start=i-(len[i]/2);
       end=i+(len[i]/2);
      
       }
  //last extract palindrome from string from x=start to y=end     
      string st="";
      for(int i=x;i<=y;++i)
      {
         if(s[i]!='$')
          st+=s[i];
      }
  
    return st;
}