OJ Board

Posted: **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.

Posted: **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?

Posted: **Tue Oct 13, 2009 12:04 pm**

I figured out the solution, thx

Posted: **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;
}

Posted: **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;
}

Posted: **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?

Posted: **Mon Sep 30, 2013 10:37 pm**

Post your full code.

Posted: **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;
		
	}
}

Posted: **Wed Oct 02, 2013 12:13 am**

Input: abaa
AC output: abaaba

Posted: **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.

Posted: **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;
}

Posted: **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

Posted: **Sat May 10, 2014 1:35 pm**

brianfry713,

Thanks for the great test cases!

Posted: **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

Posted: **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;
}

OJ Board

11475 - Extend to Palindrome

Re: 11475 - Extend to Palindromes

Re: 11475 - Extend to Palindromes

Re: 11475 - Extend to Palindromes

Re: 11475 - Extend to Palindromes

Re: 11475 - Extend to Palindromes

Re: 11475 - Extend to Palindromes

Re: 11475 - Extend to Palindromes

Re: 11475 - Extend to Palindromes

Re: 11475 - Extend to Palindromes

Re: 11475 - Extend to Palindromes

Re: 11475 - Extend to Palindromes

Re: 11475 - Extend to Palindromes

Re: 11475 - Extend to Palindromes

Re: 11475 - Extend to Palindrome

Re: 11475 - Extend to Palindrome