11475 - Extend to Palindromes

[roticv]

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.

[898989]

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.

Please, Any more hints?

[898989]

I figured out the solution, thx

[Parksungsu]

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;
}

[LegendMaker]

Why wrong answer??????????????????????????????????????????????????

Code: Select all

#include<stdio.h>
#include<string.h>
#define maxn 100000+10
char 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;
}