## 11475 - Extend to Palindrome

Moderator: Board moderators

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

### 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.

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

### 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
Contact:

### Re: 11475 - Extend to Palindromes

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

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

### 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 == rstr )
{
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
New poster
Posts: 2
Joined: Wed Oct 12, 2011 7:40 am

### Re: 11475 - Extend to Palindromes

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

alexiago
New poster
Posts: 14
Joined: Thu Jan 24, 2008 6:34 pm

### Re: 11475 - Extend to Palindromes

I tried to solve this problem using this heuristic: an index i is at the start of the string and another index j is at the end, the string s is stored in an aux array, index i keeps incrementing until it's smaller than j, and j decrements when s == s[j]. The idea behind this approach is that the start should be equal to the end, if they are different add a value equals to the start and move on the start, otherwise if they are equal just move on both indexes.
This approach worked for all sample input and a few others that I tried but I'm still getting WA.

Code: Select all

``````while(scanf("%s",s) != EOF){
len = strlen(s);
int index = 0;
int i = 0, j = len - 1;
while(i < j) {
aux[index++] = s[i];
if(s[i] == s[j])
j--;
i++;
}
for(i=0; i<=j; i++)
printf("%c",s[i]);
for(i=index-1; i>=0; i--)
printf("%c",aux[i]);
printf("\n");
}
``````
Anyone has any idea why this approach doesn't work or any counterexample?

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 11475 - Extend to Palindromes

Check input and AC output for thousands of problems on uDebug!

alexiago
New poster
Posts: 14
Joined: Thu Jan 24, 2008 6:34 pm

### Re: 11475 - Extend to Palindromes

Here's my complete code, it's basically what I posted before. Thanks in advance.

Code: Select all

``````#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>

#define MAX 100005

using namespace std;

main(){
char s[MAX], aux[MAX];
int len, index, i, j;
while(scanf("%s",s) != EOF){
len = strlen(s);
int index = 0;
int i = 0, j = len - 1;
int last = -1;
while(i < j) {
aux[index++] = s[i];
if(s[i] == s[j])
j--;
i++;
}

for(i=0; i<=j; i++)
printf("%c",s[i]);
for(i=index-1; i>=0; i--)
printf("%c",aux[i]);
cout << endl;

}
}

``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 11475 - Extend to Palindromes

Input: abaa
AC output: abaaba
Check input and AC output for thousands of problems on uDebug!

alexiago
New poster
Posts: 14
Joined: Thu Jan 24, 2008 6:34 pm

### Re: 11475 - Extend to Palindromes

I got it, my approach can add characters to the middle of the string (even though my algorithm could result in a smaller palindrome string, for your input my code returns ababa instead of abaaba). Thank you.

abcman13
New poster
Posts: 6
Joined: Sun Apr 07, 2013 6:00 am

### Re: 11475 - Extend to Palindromes

Hello everyone. Would anyone mind helping me out? What I do is run KMP over the given string searching for the longest occurence of "rev" ( the reverse of the string given ). After I find the max overlap, I take the first longitud - max_occurence characters of the string given, proceed to reverse said characters and concatenate them to the original string? Any suggestions or possible that could break my algorithm?

Code: Select all

``````#include "iostream"
#include "vector"
#include "algorithm"
using namespace std;

vector < int > v;
string str, rev, temp;

string conc( int l ){
temp = str.substr( 0, l );
reverse( temp.begin(), temp.end() );
return temp;
}

string kmp(){
int len = (int) str.size();
rev = string( str.rbegin(), str.rend() );
v.resize( len + 1, -1 );
for( int i = 1; i <= len; i++ ){
int pos = v[i-1];
while( pos != -1 && rev[pos] != rev[i-1] )
pos = v[pos];
v[i] = pos + 1;
}
for( int sp = 0, kp = 0; sp < len ; sp++ ){
while( kp != -1 && (kp == len || rev[kp] != str[sp] ) )
kp = v[kp];
kp++;
}
return conc( len - add );
}

int main(){
while( cin >> str )
cout << str << kmp() << endl;
return 0;
}``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 11475 - Extend to Palindromes

Input:

Code: Select all

``````bcad
bcebccaedbabcbbd
ecacdcae
cde
dbbcedbe
cdeaa
bbabdcabbaaecb
bedcea
aec
edacdbddedbeeca
decbbeeaaedcbcccc
bbabbaeeeaebc
bbaeccbcdbabdeedbc
bcae
debeddddbaed
ecaeaaeebec
ecc
edbcdedbdacbaabb
ebeb
dddaabbeaaebcbcabedc
dceebaccbbdcb
ebb
ecccaaaceac
ddaeaebebcaeeeedbaa
c
edabcedbebeeccbebcdd
cdddbddddd
dabcdebae
deeacabebcbcacdb
ea
bcceab
babbebcdebaca
abdcccbeacac
dd
eceedcedcbc
acb
beb
cec
bebdce
acbdddd
baeeac
dcbbaab
d
ccdbddecceabcacbbedb
ddce
bcaededbb
ccdcbcc
aa
bccebbacdaecc
bece
ccbbdacb
daaacddcdacccbeb
babdeddddcaceaaa
dcccbdeeebeacebccb
edbacbabacabecbdbc
b
ceeceeaebcdebabeaee
ebbdee
bbdeddebbabbcccecdb
ecd
d
``````
AC output:

Code: Select all

``````bcadacb
bcebccaedbabcbbdbbcbabdeaccbecb
ecacdcaeacdcace
cdedc
dbbcedbebdecbbd
cdeaaedc
bbabdcabbaaecbceaabbacdbabb
bedceaecdeb
aecea
decbbeeaaedcbccccbcdeaaeebbced
bbabbaeeeaebcbeaeeeabbabb
bbaeccbcdbabdeedbcbdeedbabdcbcceabb
bcaeacb
debeddddbaedeabddddebed
ecaeaaeebecebeeaaeace
ecce
ebebe
dceebaccbbdcbcdbbccabeecd
ebbe
ecccaaaceacaecaaaccce
c
cdddbdddddbdddc
deeacabebcbcacdbdcacbcbebacaeed
eae
bcceabaeccb
babbebcdebacabedcbebbab
abdcccbeacacaebcccdba
dd
eceedcedcbcdecdeece
acbca
beb
cec
bebdcecdbeb
acbddddbca
baeeacaeeab
dcbbaabbcd
d
ccdbddecceabcacbbedbdebbcacbaecceddbdcc
ddcecdd
bcaededbbdedeacb
ccdcbccbcdcc
aa
beceb
babdeddddcaceaaaecacddddedbab
dcccbdeeebeacebccbecaebeeedbcccd
edbacbabacabecbdbcebacababcabde
b
ceeceeaebcdebabeaeeaebabedcbeaeeceec
ebbdeedbbe
bbdeddebbabbcccecdbdcecccbbabbeddedbb
ecdce
d
``````
Check input and AC output for thousands of problems on uDebug!

uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

### Re: 11475 - Extend to Palindromes

brianfry713,

Thanks for the great test cases!
Check input and AC output for over 7,500 problems on uDebug!

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 11475 - Extend to Palindrome

gr81, I glanced at your code at:
http://ideone.com/ulpHXV

Since it is getting RE, I looked and tested for likely causes. One that came up is:
http://www.cplusplus.com/reference/stri ... ng/substr/
string substr (size_t pos = 0, size_t len = npos) const;
pos
If this is greater than the string length, it throws out_of_range.

If you insert this code before line 75, you get WA instead of RE:
if(index >= rev.length())
exit(0);

So something is wrong with your algorithm. Try recoding it.
http://en.wikipedia.org/wiki/Knuth%E2%8 ... _algorithm
Check input and AC output for thousands of problems on uDebug!

Nahian.Sunny
New poster
Posts: 6
Joined: Tue Oct 21, 2014 12:51 pm

### Re: 11475 - Extend to Palindrome

Can anyone plz help?? Why WA ??? My output matches with all test cases ... still WA!!

Code: Select all

``````#include <iostream>
#include <algorithm>
#include <fstream>
#include <string>
#include <iostream>

using namespace std;

string input;

int is_palli()
{
int i,n=input.size();
for(i=0;i<n/2;i++)
{
if(input[i]!=input[n-1-i])
return 0;
}
return 1;
}

int main()
{
char ch;
int i,j,m,n,k,t;
ofstream out("output.txt");
while(getline(cin,input))
{
if(is_palli()==1)
cout << input << endl;
else
{
n=input.size();
m=0;
ch=input[n-1];t=0;
for(i=0;i<n-1;i++)
{
t=0;
if(input[i]==input[n-1]){
for(j=i,k=n-1;j<n-1;j++,k--)
{
if(input[j]==ch && t==0)
t=j-1;
if(input[j]!=input[k])
break;
}
if((j-i)>m && j==n-1)
{
m=j-i;
}
}
if(t>0)
i=j-1;
}
for(i=0,j=(n-2-m);j>=0;i++,j--){
input.push_back(input[j]);
}

cout << input << endl;
out << input << endl;
}
}
out.close();
return 0;
}

``````