353 - Pesky Palindromes

[Dmytro Chernysh]

I got AC, but I spent too much memory - the worst one on the ranklist
However, I see a lot of people got AC only with 64K. How???

[LawrenceT]

all you need is the original string, which should be a character array of size 81, and a array storing the avaliable start positions.

the way i do this question is to find all palindromes of length i, before moving on to find palindromes of length i + 1. It is easy to eliminate all duplicates just by keeping another boolean array the same length as the string.

hope this helps without spoiling the problem.

[miras]

Hello ....

Tell me sth. what is the output for sth like that


BTW. this input can be not good (i don't know.,....))

Code: Select all

aAa
 AAAAAAAAAAAAAAAAAAAAAAmirasAAAAAAAAAAAAAA
A   A

my outpur...

Code: Select all

The string 'aAa' contains 3 palindromes.
The string 'A  A' contains 4 palindromes.

What do u think about it ???




___________________________________________
Regards MIras

[sohel]

Your output seems to be correct for the two you have mentioned but what about the second case of your input.

[miras]

hey what test are u thikking about... ??

[Corpse Fiend]

Question:
If I have only 1 palindrome as my output should I print:
1. The string 'a' contains 1 palindrome.
-or-
2. The string 'a' contains 1 palindromes.

BTW, if you can post here some complex tests I'd be grateful.
My programm gets WA, but I don't know what's wrong with it. All test cases that I was thinking about are going OK .

[IRA]

Why WA!?
I can't find my bug...
Please help me to find the bug.
Thanks in advance!

Code: Select all

I got AC.

[almorales]

I got CE but I don't know why. Would you help me ? This is my code:

#include <cstring.h>
#include <iostream.h>
char e[80];int cant_cads=0;
int piv_cadenitas=0;string cadenitas[3240];
bool Palindrome(char* a)
{
int b = (int)strlen(a);bool result;int c=0,d=b-1;
if (b == 1)
{result = true;}
else
{
if (b%2==0)
{
while ( c<d && a[c]==a[d])
{c++;d--;}
result = !(c < d);
}
else
{
while ( c!=d && a[c]==a[d])
{c++;d--;}
result = c == d;
}
}
return result;
}

bool Estaba(string str)
{
bool result;int i=0;
while (cadenitas!=str && i<piv_cadenitas)
{i++;}
if(i==piv_cadenitas)
{result=false;}
else
{result=true;}
return result;
}

void Principal()
{
int longi = (int)strlen(e)-1;
for (int i=0;i<=longi;i++)
for (int j=i;j<=longi;j++)
{
char* aux = new char[j-i+2];aux[j-i+1]=0;int piv_aux=0;
for (int z=i;z<=j;z++)
{aux[piv_aux++]=e[z];}
if (Palindrome(aux))
{
if (Estaba(aux)==false)
{
cant_cads++;
cadenitas[piv_cadenitas++]=(string)aux;
}
}
}
}
int main()
{
while (gets(e))
{
Principal();
printf(" The string '");
printf("%s",e);
printf("' contains ");
printf("%i",cant_cads);
printf(" palindromes.\n");
for (int m=0;m<(int)strlen(e);m++)
{e[m]=0;}
cant_cads=0;piv_cadenitas=0;
}
return 0;
}
//---------------------------------------------------------------------------

[almorales]

test

[ashis.csedu]

Miras, is your second case's output OK?

Code: Select all

A***A

your output is 4. But aren't there 5 palindromes?

Code: Select all

A
A***A
*
**
***

Though i'm getting WA
Can you please send me more test cases..??

Ashis, CSEDU

[ashis.csedu]

Miras's input:

Code: Select all

aAa 
 AAAAAAAAAAAAAAAAAAAAAAmirasAAAAAAAAAAAAAA 
A   A

My output: (yet getting WA):(

Code: Select all

The string 'aAa ' contains 4 palindromes.
The string ' AAAAAAAAAAAAAAAAAAAAAAmirasAAAAAAAAAAAAAA ' contains 28 palindromes.
The string 'A   A' contains 5 palindromes.

Is there anybody verify this? Can you give some more critical I/Os?

Ashis

[ashis.csedu]

My previous post was a mistake cause i copied Miras's input with mouse and pasted, so a trailing space character can be seen in my output. Now i've corrected the input, now my output is -

Code: Select all

The string 'aAa' contains 3 palindromes.
The string ' AAAAAAAAAAAAAAAAAAAAAAmirasAAAAAAAAAAAAAA' contains 28 palindromes.
The string 'A   A' contains 5 palindromes.

Thanks.

[Jan]

There are no spaces in the input file. However, you can post your code.

[ashis.csedu]

Jan,
I'm getting WA in the following code. can you find bugs in my code? Can you give some test cases too.

Code: Select all

Removed after accepted.

Thanks.

[Jan]

Ashis vai, it look a long time. Your code seems 99.99% correct. But just imagine that, a string with 80 characters are given, and is a palindrome. Then your code will fail. Guess why? You have used

Code: Select all

char temp[80];

Use 81 or more. Hope it helps.