## 11475 - Extend to Palindromes

Moderator: Board moderators

### Re: 11475 - Extend to Palindromes

Well let me drop one hint.

In this problem we have to find the suffix of the string that is the longest palindrome. This problem can be solved using a slightly modified KMP with the search string the reverse of the original string.

Therefore, this problem can be solved in linear time.
roticv
Learning poster

Posts: 63
Joined: Sat Dec 11, 2004 9:28 am

### Re: 11475 - Extend to Palindromes

I have solved the problem using hashing, but do not know how to modify KMP to find answer.
What I understood, solving following the problem will be the solution : Given String, Find longest prefix that is palindrome. Correct me if i am wrong.
Also it is same as given string A, and its reversed one B, find longest prefix in A that is equal to suffix in B.
The only relation to KMP, is that its failure function at idx i, find longest prefix in substring [0,i] that is equal to suffix in this substring. I do not know If i am on correct track or not, and how to use this note.

Sleep enough after death, it is the time to work.
898989
Learning poster

Posts: 83
Joined: Wed Feb 01, 2006 12:59 pm
Location: (Fci-cu) Egypt

### Re: 11475 - Extend to Palindromes

I figured out the solution, thx
Sleep enough after death, it is the time to work.
898989
Learning poster

Posts: 83
Joined: Wed Feb 01, 2006 12:59 pm
Location: (Fci-cu) Egypt

### Re: 11475 - Extend to Palindromes

I tried to problem 11475 Extend Parindrome. But I don't receive Acepted. Why i got a TLE??

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

string Knuth_Morris_Pratt(string str, string rstr)
{
static string temp;
for(int i = 0; i < str.size(); i++)
{
if( str[i] == rstr[0] )
{
for(int j = 0, k = i; j < rstr.size();j++)
{
if( k == str.size()-1 )
{
bool bParindrome = true;
for(int m = i, n = j; m >= 0; m--, n++)
{
if( str[m] != rstr[n])
{
bParindrome = false;
}
}

if(bParindrome)
{
string t;
t.resize(rstr.size() - j);
copy(rstr.begin()+(j+1), rstr.end(), t.begin());
temp = str;
temp += t;

return temp;
}
else break;
}
else if( str[k] != rstr[j] )
break;
else k++;
}
}
}

return temp;
}

int main()
{
static string str,rstr;
while(cin >> str && !str.empty())
{
rstr = str;
reverse(rstr.begin(), rstr.end());

cout << (equal(str.begin(), str.end(), rstr.begin())? str : Knuth_Morris_Pratt(str, rstr)) << endl;
}

return 0;
}
Parksungsu
New poster

Posts: 5
Joined: Sun Aug 15, 2010 2:56 am

### Re: 11475 - Extend to Palindromes

Code: Select all
`#include<stdio.h>#include<string.h>#define maxn 100000+10char a[maxn],b[maxn],next[maxn];void NEXT(int len){   int i,j;   next[0]=j=-1;   for(i=1;i<len;i++)   {      while(j>-1&&b[j+1]!=b[i])         j=next[j];      if(b[j+1]==b[i])         j++;      next[i]=j;   }}int KMP(int len){   NEXT(len);   int i,j;   for(i=0,j=-1;i<len;i++)   {      while(j>-1&&b[j+1]!=a[i])         j=next[j];      if(b[j+1]==a[i])         j++;   }   return len-j-1;}int main(){   int len,i,j,temp;   while(gets(a))   {      len=strlen(a);      for(i=len-1,j=0;i>=0;i--)         b[j++]=a[i];      b[j]=0;      temp=KMP(len);      for(i=0;i<temp;i++)         putchar(a[i]);      puts(b);   }   return 0;}`
LegendMaker
New poster

Posts: 2
Joined: Wed Oct 12, 2011 7:40 am

Previous