## 11151 - Longest Palindrome

Moderator: Board moderators

### 11151 - Longest Palindrome

hmm.. It's so tricky. It just looks like an easy problem, but I received WA repeatedly... Is there any critical input?
I love Problem Solving!!!
soyoja
Experienced poster

Posts: 106
Joined: Sun Feb 17, 2002 2:00 am
Location: Seoul, South Korea

### Re: 11151 Longest Palindrome

soyoja wrote:Is there any critical input?

My code takes emtpy string as input.

emotional blind
A great helper

Posts: 383
Joined: Mon Oct 18, 2004 8:25 am

### 11151 WA

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;
}
Karim
New poster

Posts: 7
Joined: Sun Sep 24, 2006 4:11 pm

Try this input :

Code: Select all
`1qweqweqwedadqweqweqwe`

I think the output should be :

Code: Select all
`3`

CMIW...
jan_holmes
Experienced poster

Posts: 136
Joined: Fri Apr 15, 2005 3:47 pm
Location: Singapore

jan_holmes wrote:Try this input :

Code: Select all
`1qweqweqwedadqweqweqwe`

I think the output should be :

Code: Select all
`3`

CMIW...

Oput should be
Code: Select all
`13`

emotional blind
A great helper

Posts: 383
Joined: Mon Oct 18, 2004 8:25 am

### I still got WA

Here is my trying input
Code: Select all
`12ADAMMADAMqweqweqwedadqweqweqweaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabcdefghijklmnopqrstuvwxyzabcdefhhabcabcabc0101010101aabefgba`

Line with nothing is empty string

Code: Select all
`350130255125915`

FAQ
Learning poster

Posts: 84
Joined: Wed Jan 28, 2004 6:23 pm

### Take the entire line as input

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.
MAK
New poster

Posts: 28
Joined: Sun Oct 23, 2005 3:44 pm

Correct output

emotional blind
A great helper

Posts: 383
Joined: Mon Oct 18, 2004 8:25 am

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

Posts: 48
Joined: Wed Jun 07, 2006 6:26 pm
Location: Georgia Tbilisi

Giorgi wrote: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`
Last edited by artie on Mon Jan 01, 2007 5:23 am, edited 1 time in total.
artie
New poster

Posts: 8
Joined: Sun Dec 31, 2006 11:56 am
Location: Russia

artie wrote: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);    ...    ...}`
helloneo
Guru

Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

helloneo wrote:
artie wrote: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?
artie
New poster

Posts: 8
Joined: Sun Dec 31, 2006 11:56 am
Location: Russia

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
temper_3243
Experienced poster

Posts: 105
Joined: Wed May 25, 2005 7:23 am

Can u Explain your algorithm ..???

Thanks
Karim
New poster

Posts: 7
Joined: Sun Sep 24, 2006 4:11 pm

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[i]==string[j]
= max( largest(i+1,j), largest(i,j-1) )

hope it helps

emotional blind
A great helper

Posts: 383
Joined: Mon Oct 18, 2004 8:25 am