10262 - Suffidromes

[Ivan Golubev]

Is empty word (i.e. with length == 0) palindrome or not?

[Adrian Kuegel]

yes, it is a palindrom

[Ivan Golubev]

OK, thanks. And one more question -- can x be a zero-length word?

[Adrian Kuegel]

Yes, for example input:
a
ab
Output:

(blank line)

[Ivan Golubev]

Thanks one more time!

[Yarin]

I keep getting WA, I'm not sure why the following algorithm doesn't work:

1) If strings equal, print "No solution."
2) If one string is empty:
2.1) If the other string is not a palindrome, print blank line
2.2) Otherwise either add 'a' or 'b' (just check which one makes the other string not a palindrome)
3) Let x be all prefixes of a and b (including whole a and b) and check whether it satifies the criteria. Select shortest and alphabetically first
4) If still no solution is found, let x be any lower case character (loop through a-z, maybe only a-b is necessary) plus the shortest of the two strings a and b. Break the loop if conditions are satisfied.
5) Print x or "No solution."

Where's the flaw!? Or have I simple missed something in the implementation of this algorithm?

[Yarin]

*sigh* I totally forgot that the string compare should be reversed since the prefix is appended backwards.

[Whinii F.]

I personally don't like posting long sources..
but anyway I'm getting too much WA

Where's my flaw? It passes every test cases I could think of.

[c]
#include <stdio.h>
#include <string.h>

#define max 2020

int al, bl;
char a[max], b[max];

void reverseString(int len, const char *from, char *to)
{
int i;
for(i = 0; i < len; i++)
to[len-i-1] = from;
to[len] = 0;
}

int isPalindrome(int len, char *str)
{
int i;
for(i = 0; i < len; i++)
if(str != str[len-i-1])
return 0;
return 1;
}

int Check(int cl, char *candidate)
{
int ap, bp;
strcpy(a+al, candidate);
strcpy(b+bl, candidate);
ap = isPalindrome(al+cl, a);
bp = isPalindrome(bl+cl, b);
a[al] = b[bl] = 0;
return ap ^ bp; /* xor */
}

void solve(void)
{
int i;
int xl = -1, cl;
char x[max], c[max]; /* c stands for Candidate */

al = strlen(a);
bl = strlen(b);

c[0] = 0;
if(Check(0, c))
{
printf("\n");
return;
}

c[1] = 0;
for(i = 'a'; i <= 'z'; i++)
{
c[0] = i;
if(Check(1, c))
{
printf("%s\n", c);
return;
}
}

reverseString(al, a, c);
cl = al;
while(cl >= 0)
{
if(Check(cl, c) && (xl == -1 || xl > cl || (xl == cl && strcmp(x, c) > 0)))
{
strcpy(x, c);
xl = cl;
}
for(i = 0; i < cl; i++)
c = c[i+1];
cl--;
}
reverseString(bl, b, c);
cl = bl;
while(cl >= 0)
{
if(Check(cl, c) && (xl == -1 || xl > cl || (xl == cl && strcmp(x, c) > 0)))
{
strcpy(x, c);
xl = cl;
}
for(i = 0; i < cl; i++)
c = c[i+1];
cl--;
}

if(xl > -1)
printf("%s\n", x);
else
printf("No solution.\n");
}

int main(void)
{
a[0] = b[0] = 0;
gets(a);
gets(b);
while(a[0] != 0 || b[0] != 0 || !feof(stdin))
{
solve();
a[0] = b[0] = 0;
gets(a);
gets(b);
}
return 0;
}[/c]

[jingye]

Try the test cases at the Waterloo ACM website

[stcheung]

Hmm....any idea why I keep getting Time Limit Exceeded? I admit my algorithm is plain, but I think it's still acceptable. Is it that I used cin.eof() wrongly or something like that? THANKS.

[cpp]#include <iostream.h>
#include <stdlib.h>
#include <string>

string A, B, longer, shorter, x1, x2;

void findpalindromes(int len);
bool palindrome(string s);
string reverse(string s);
int main()
{
while(true)
{
getline(cin, A);
getline(cin, B);
longer = (A.length() >= B.length() ? A : B);
shorter = (longer==A ? B : A);
if(cin.eof())
break;
if(longer == shorter)
{
cout << "No solution.\n";
continue;
}
if((palindrome(longer) && !palindrome(shorter)) ||
(palindrome(shorter) && !palindrome(longer)))
{
cout << "\n";
continue;
}
else if(shorter=="")
{
if(!palindrome(longer))
{
cout << "\n";
continue;
}
for(int i=0; i<26; i++)
{
if(!palindrome(longer + (char)(i + 'a')))
{
cout << (char)(i + 'a') << "\n";
break;
}
}
continue;
}

for(int len=1; len<=shorter.length(); len++)
{
findpalindromes(len);
if(x1 != "" && x2 != "")
{
cout << (x1 < x2 ? x1 : x2) << "\n";
break;
}
else if(x1 != "")
{
cout << x1 << "\n";
break;
}
else if(x2 != "")
{
cout << x2 << "\n";
break;
}
}
}
return 0;
}

void findpalindromes(int len)
{
x1 = x2 = "";
int i,j;
/* if(len > shorter.length())
{
for(i=0; i<26; i++)
{
x1 = (char)('a' + i) + reverse(shorter);
if(palindrome(shorter+x1) && !palindrome(longer + x1))
break;
}
}
else */
{
x1 = reverse(shorter.substr(0,len));
if(!palindrome(shorter + x1) || palindrome(longer + x1))
x1 = "";
}
/*
if(len > longer.length())
{
for(j=0; j<26; j++)
{
x2 = (char)('a' + j) + reverse(longer);
if(palindrome(longer+x2) && !palindrome(shorter + x2))
break;
}
}
else*/
{
x2 = reverse(longer.substr(0,len));
if(!palindrome(longer + x2) || palindrome(shorter + x2))
x2 = "";
}
}

string reverse(string s)
{
string result="";
for(int i=0; i<s.length(); i++)
{
result = s + result;
}
return result;
}

bool palindrome(string s)
{
return s == reverse(s);
}[/cpp]

[anisalamgir]

hey...
any one give me this problem algorithm..........
i can't understood...................
ok... best of luck

[soth]

I have tried a lot of inputs including test cases like the ones posted before, but I still get WA.
Some rare I/O to check where my program fails?
Thanks!

[soth]

please, does somebody have some rare IO for this problem?
I still get WA...