11475 - Extend to Palindrome

All about problems in Volume 114. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

Re: 11475 - Extend to Palindromes

Post by roticv » Sun May 31, 2009 8:53 am

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

Post by 898989 » Sat Oct 10, 2009 4:24 pm

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?
Sleep enough after death, it is the time to work.
Mostafa Saad

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

Re: 11475 - Extend to Palindromes

Post by 898989 » Tue Oct 13, 2009 12:04 pm

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

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

Re: 11475 - Extend to Palindromes

Post by Parksungsu » Sun Aug 15, 2010 9:11 am

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[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
New poster
Posts: 2
Joined: Wed Oct 12, 2011 7:40 am

Re: 11475 - Extend to Palindromes

Post by LegendMaker » Fri Jan 27, 2012 12:46 pm

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

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

Re: 11475 - Extend to Palindromes

Post by alexiago » Sat Sep 28, 2013 3:23 am

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

Post by brianfry713 » Mon Sep 30, 2013 10:37 pm

Post your full code.
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

Post by alexiago » Mon Sep 30, 2013 11:17 pm

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

Post by brianfry713 » Wed Oct 02, 2013 12:13 am

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

Post by alexiago » Wed Oct 02, 2013 11:04 pm

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

Post by abcman13 » Mon Nov 04, 2013 4:15 am

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;
     }
     int add = 0;
     for( int sp = 0, kp = 0; sp < len ; sp++ ){
          while( kp != -1 && (kp == len || rev[kp] != str[sp] ) )
               kp = v[kp];
          kp++;
          add = max( add, 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

Post by brianfry713 » Tue Nov 05, 2013 2:06 am

Input:

Code: Select all

bcad
bcebccaedbabcbbd
ecacdcae
cde
dbbcedbe
cdeaa
bbabdcabbaaecb
bedcea
aec
edacdbddedbeeca
decbbeeaaedcbcccc
bbabbaeeeaebc
bbaeccbcdbabdeedbc
deaddaaebd
abbbaededbadaeeeecb
bcae
cbcdacebdaecadddd
debeddddbaed
deccbedad
ecaeaaeebec
ecc
edbcdedbdacbaabb
daabebcadbc
ecceabceeadbdbbadea
ebeb
dddaabbeaaebcbcabedc
dceebaccbbdcb
eebeebacadcaedae
ebb
ecccaaaceac
ddaeaebebcaeeeedbaa
c
edabcedbebeeccbebcdd
cdddbddddd
daecbdeabdcead
dcdcbacbadceba
baedcadbcecedec
dabcdebae
caceeeeaedacadbeecdc
deeacabebcbcacdb
ea
bcceab
cedad
babbebcdebaca
abdcccbeacac
aeeeabadcddbaebcbaec
ecdadd
dcedcdcebeaeddadedc
dd
eceedcedcbc
acb
abcebcbbbcaeadabbb
beb
dadba
cec
bebdce
eebcabadadeebaebaa
edddaccccadebdb
deedeccadeacec
acbdddd
badcbd
adaebbdaedebaadd
baeeac
dcbbaab
adbccbebaecceadc
adcaadeeccecaceeddb
d
ccdbddecceabcacbbedb
ddce
bcaededbb
acbeebabeeeadedbede
ccdcbcc
aa
aeabdcebbdadcbcabaec
bccebbacdaecc
bece
ccbbdacb
baaade
bacadeaabaddcdcba
daaacddcdacccbeb
eadeddadcabe
bccecbccbadde
babdeddddcaceaaa
dcccbdeeebeacebccb
caccecedabbeadbcc
edbacbabacabecbdbc
b
ceeceeaebcdebabeaee
ebbdee
cbdaeebdeadacddd
aaddbaddbb
caabbadaaeaeceeeeee
bbdeddebbabbcccecdb
ecd
dcccdccadcbdbdbea
adaaeedaceeabc
abdeadddcdb
aaadbdabceb
d
eedebeceadaddcee
AC output:

Code: Select all

bcadacb
bcebccaedbabcbbdbbcbabdeaccbecb
ecacdcaeacdcace
cdedc
dbbcedbebdecbbd
cdeaaedc
bbabdcabbaaecbceaabbacdbabb
bedceaecdeb
aecea
edacdbddedbeecaceebdeddbdcade
decbbeeaaedcbccccbcdeaaeebbced
bbabbaeeeaebcbeaeeeabbabb
bbaeccbcdbabdeedbcbdeedbabdcbcceabb
deaddaaebdbeaaddaed
abbbaededbadaeeeecbceeeeadabdedeabbba
bcaeacb
cbcdacebdaecaddddaceadbecadcbc
debeddddbaedeabddddebed
deccbedadebcced
ecaeaaeebecebeeaaeace
ecce
edbcdedbdacbaabbaabcadbdedcbde
daabebcadbcbdacbebaad
ecceabceeadbdbbadeaedabbdbdaeecbaecce
ebebe
dddaabbeaaebcbcabedcdebacbcbeaaebbaaddd
dceebaccbbdcbcdbbccabeecd
eebeebacadcaedaeadeacdacabeebee
ebbe
ecccaaaceacaecaaaccce
ddaeaebebcaeeeedbaabdeeeeacbebeaeadd
c
edabcedbebeeccbebcddcbebcceebebdecbade
cdddbdddddbdddc
daecbdeabdceadaecdbaedbcead
dcdcbacbadcebabecdabcabcdcd
baedcadbcecedececbdacdeab
dabcdebaeabedcbad
caceeeeaedacadbeecdceebdacadeaeeeecac
deeacabebcbcacdbdcacbcbebacaeed
eae
bcceabaeccb
cedadec
babbebcdebacabedcbebbab
abdcccbeacacaebcccdba
aeeeabadcddbaebcbaeceabcbeabddcdabaeeea
ecdaddadce
dcedcdcebeaeddadedcdedaddeaebecdcdecd
dd
eceedcedcbcdecdeece
acbca
abcebcbbbcaeadabbbadaeacbbbcbecba
beb
dadbabdad
cec
bebdcecdbeb
eebcabadadeebaebaabeabeedadabacbee
edddaccccadebdbedaccccaddde
deedeccadeacecaedaccedeed
acbddddbca
badcbdbcdab
adaebbdaedebaaddaabedeadbbeada
baeeacaeeab
dcbbaabbcd
adbccbebaecceadcdaecceabebccbda
adcaadeeccecaceeddbddeecacecceedaacda
d
ccdbddecceabcacbbedbdebbcacbaecceddbdcc
ddcecdd
bcaededbbdedeacb
acbeebabeeeadedbedebdedaeeebabeebca
ccdcbccbcdcc
aa
aeabdcebbdadcbcabaeceabacbcdadbbecdbaea
bccebbacdaecceadcabbeccb
beceb
ccbbdacbcadbbcc
baaadedaaab
bacadeaabaddcdcbabcdcddabaaedacab
daaacddcdacccbebcccadcddcaaad
eadeddadcabebacdaddedae
bccecbccbaddeddabccbceccb
babdeddddcaceaaaecacddddedbab
dcccbdeeebeacebccbecaebeeedbcccd
caccecedabbeadbccbdaebbadececcac
edbacbabacabecbdbcebacababcabde
b
ceeceeaebcdebabeaeeaebabedcbeaeeceec
ebbdeedbbe
cbdaeebdeadacdddcadaedbeeadbc
aaddbaddbbddabddaa
caabbadaaeaeceeeeeeceaeaadabbaac
bbdeddebbabbcccecdbdcecccbbabbeddedbb
ecdce
dcccdccadcbdbdbeaebdbdbcdaccdcccd
adaaeedaceeabcbaeecadeeaada
abdeadddcdbdcdddaedba
aaadbdabcebecbadbdaaa
d
eedebeceadaddceecddadaecebedee
Check input and AC output for thousands of problems on uDebug!

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

Re: 11475 - Extend to Palindromes

Post by uDebug » Sat May 10, 2014 1:35 pm

brianfry713,

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

Find us on Facebook. Follow us on Twitter.

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

Re: 11475 - Extend to Palindrome

Post by brianfry713 » Sat Dec 20, 2014 2:51 am

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

Post by Nahian.Sunny » Thu Jan 01, 2015 12:52 pm

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


Post Reply

Return to “Volume 114 (11400-11499)”