11151 - Longest Palindrome

[soyoja]

hmm.. It's so tricky. It just looks like an easy problem, but I received WA repeatedly... Is there any critical input?

[emotional blind]

Is there any critical input?

My code takes emtpy string as input.
What about yours?

[Karim]

I am getting wrong answer but i dont know why

can anyone tell me

Here is the code

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;

string s,t1,t2;

int main()
{
//freopen("d.in","rt",stdin);
int t;
int i,j;

cin>>t;
getline(cin,s);
for(i=0;i<t;i++)
{
getline(cin,s);
if(s=="")
{
cout<<"0"<<endl;
continue;
}
for(j=0;j<s.length();j++)
{
t1 = s.substr(0,s.length()-j);
t2 = s.substr(0,s.length()-j);
reverse( t1.begin() , t1.end() );
if(t1 == t2)
{
cout<<t1.length()<<endl;
break;
}
t1 = s.substr(j);
t2 = s.substr(j);
reverse( t1.begin() , t1.end() );
if(t1 == t2 )
{
cout<<t1.length()<<endl;
break;
}
}
}
return 0;
}

[jan_holmes]

Try this input :

Code: Select all

1
qweqweqwedadqweqweqwe

I think the output should be :

Code: Select all

3

CMIW...

[emotional blind]

Try this input :

Code: Select all

1
qweqweqwedadqweqweqwe

I think the output should be :

Code: Select all

3

CMIW...

Oput should be

Code: Select all

13

[FAQ]

Here is my trying input

Code: Select all

12
ADAM
MADAM

qweqweqwedadqweqweqwe

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
abcdefghijklmnopqrstuvwxyz
abcdefhh
abcabcabc
0101010101
a
abefgba

Line with nothing is empty string

Code: Select all

3
5
0
13
0
255
1
2
5
9
1
5

some more tricky tests please?

[MAK]

Yes, instead of taking a string (cin>>line in C++), take the entire line as input (use cin.getline). That way, even if the line is empty, it is still considered as valid input.

[emotional blind]

Correct output

[Giorgi]

there is no critical input. what algorithm did you use?

[artie]

there is no critical input. what algorithm did you use?

Hi. I am newcomer in c++ language. I got ac in the contest with pascal, but same algorithm in c++ got wa. I wish somebody explain me, what is wrong in c++ code:

Code: Select all

got AC

[helloneo]

Hi. I am newcomer in c++ language. I got ac in the contest with pascal, but same algorithm in c++ got wa. I wish somebody explain me, what is wrong in c++ code:

Taking input is faulty..
I don't know exactly what it is.. but try this..

Code: Select all

scanf("%d", &t);
gets(s);
while (t--) {
    gets(s);
    ...
    ...
}

[artie]

Hi. I am newcomer in c++ language. I got ac in the contest with pascal, but same algorithm in c++ got wa. I wish somebody explain me, what is wrong in c++ code:

Taking input is faulty..
I don't know exactly what it is.. but try this..

Code: Select all

scanf("%d", &t);
gets(s);
while (t--) {
    gets(s);
    ...
    ...
}

Thanks a lot!
Could anyone explain me why my input was faulty?

[temper_3243]

It is a known problem. You cannot mix scanf and gets . Use scanf or gets but not both in the same program.

What happens is scanf("%d",&t) reads an integer and then stops. So the buffer has \n . now when gets reads it gets an empty line. Also don't use gets use fgets . Don't mix fgets and scanf . Use fgets and then use strtoul for integer conversion

http://c-faq.com/stdio/scanfinterlace.html

[Karim]

Can u Explain your algorithm ..???

Thanks

[emotional blind]

there is a recurence relation

largest(i,j) // largest pelindrom in between index i and j including i and j
= 1, where i=j
= largest(i+1,j-1)+2, where i!=j and string==string[j]
= max( largest(i+1,j), largest(i,j-1) )

hope it helps