# Using manacher algorithm. C++ solution.

• ``````class Solution {
public:
string longestPalindrome(string s)
{
return manacher(s);
}
private:
string manacher(string s)
{
string str(s.length() * 2 + 1, '#');
int k = 0;
for (int i = 0; i < s.length(); ++i)
{
str[k++] = '#';
str[k++] = s[i];
}
str[k] = '#';

int n = str.length();
int mostRight = 0;
int mostRightIdx = 0;
int *p = new int[n];

for (int i = 0; i < n; ++i)
{
if (mostRight > i)
p[i] = min(p[2 * mostRightIdx - i], mostRight - i);
else
p[i] = 1;

while (i - p[i] >= 0 && i + p[i] < n && str[i - p[i]] == str[i + p[i]])
p[i]++;

if (i + p[i] > mostRight)
{
mostRight = i + p[i];
mostRightIdx = i;
}
}

for (int i = 0; i < n; ++i)
{
{
}
}

int len = 0;
if (maxRadis % 2 == 0)
else
len = maxRadis / 2 * 2;

string ans(len, ' ');
k = 0;
for (int i = maxRadisIdx - maxRadis + 1, cnt = 0; cnt < maxRadis; i += 2, cnt++)
ans[k++] = str[i + 1];

return ans;
}
};``````

• Don't look at my code at first, just Google about "manacher algorithm", when you understand the algorithm then look back to my code.

• #include<iostream>
#include<conio.h>
#include<string.h>
using namespace std;

void input(char a[],int sza)
{
for(int i=0;i<sza;i++)
{
cin>>a[i];
}

}

void print(char a[],int start, int b)
{
for(int j=start;j<=b;j++)
{
cout<<a[j];
}

}

void func(char a[],int sza)
{
int high,low,start,maxlength=1; //maxlength is the answer i.e. length of longest palindrome in substring
for(int i=1;i<sza;i++)
{
//the follwoing code is for even length palindrome with i-1 and i as center;
low=i-1;
high=i;

while(low>=0 && high<sza && a[low]==a[high])
{
if((high-low+1)>maxlength)
{
start=low;
maxlength=high-low+1;
}
low--;
high++;

}

``````// the following code is for odd length palindrome with i as center
low=i-1;
high=i+1;
while(low>=0 && high<sza && a[low]==a[high])
{
if((high-low+1)>maxlength)
{
start=low;
maxlength=high-low+1;
}
low--;
high++;
}
``````

}

cout<<endl<<"printing the substring palindrome : "<<endl;
print(a,start,start+maxlength-1);

}

int main()
{
char a[15],b[15];
int sza; //sza is size of d array
cout<<endl<<"enter d size of array or string"<<endl;
cin>>sza;
input(a,sza);
func(a,sza);
return 0;
}

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.