I have read these discussion....Fix my code.... but still I got WA... Plz help.......Here is my code
#include<stdio.h>
#include<string.h>
//#include<conio.h>
char x[2000],y[2000];
long i,j,d,l,m,n,c[2000][2000],b[2000][2000];
long lcslength(){
m=strlen(x);
n=strlen(y);
for(i=1;i<=m;i++)c[0]=0;
for(j=0;j<=n;j++) c[0][j]=0;
for(i=1;i<=m;i++)
for(j=1;j<=n;j++){
if(x[i-1]==y[j-1]){
c[j]=c[i-1][j-1]+1;
b[j]=1; }
else if(c[i-1][j]>=c[j-1]){
c[j]=c[i-1][j];
b[j]=2;
}
else{
c[j]=c[j-1];
b[j]=3;
}
}
return c[m][n];
}
int main(){
gets(x);
sscanf(x,"%ld",&d);
while(d--){
gets(x);
n=strlen(x);
j=0;
for(i=n-1;i>=0;i--){
y[j]=x;
j++; }
printf("%ld\n",lcslength());
}
//getch();
return 0;
}
11151 - Longest Palindrome
Moderator: Board moderators
Re: 11151 - Longest Palindrome
Im getting TLE altough it takes no time in solving a 1000 letter palindrome,
any ideas??
Thanx
any ideas??
Code: Select all
# include <iostream>
#include <string>
#include <math.h>
#include <algorithm>
using namespace std;
string s;
const int SIZE = 10001;
int dp [SIZE][SIZE];
void Initialize ()
{
for (int i = 0 ; i < SIZE ; i++)
for (int j = 0 ; j < SIZE ; j++)
dp[i][j]=-1;
}
int longestPalindrom (int i , int j)
{
if (dp[i][j]!=-1)
return dp[i][j];
if (i>j )
return 0;
if (i == j)
return 1;
if (i<j && s[i]==s[j])
{
dp[i][j] = 2+ longestPalindrom(i+1, j-1);
return dp[i][j];
}
if (i<j && s[i]!=s[j])
{
dp[i][j]= max(longestPalindrom(i+1,j),longestPalindrom(i,j-1));
return dp[i][j];
}
}
int main()
{
int t ;
cin >> t;
cin.ignore();
while(t--)
{
Initialize();
getline(cin,s);
cout<<longestPalindrom(0,s.size()-1)<<endl;
}
}
Re: 11151 - Longest Palindrome
Did you try changing this line
to
![:)](./images/smilies/icon_smile.gif)
Code: Select all
const int SIZE = 10001;
Code: Select all
const int SIZE = 1001;
![:)](./images/smilies/icon_smile.gif)
-
- New poster
- Posts: 39
- Joined: Tue Aug 07, 2012 10:40 pm
- Location: BUBT,Dhaka, Bangladesh
- Contact:
Re: 11151 - Longest Palindrome
Input:
Output:
Code: Select all
10
aab
bba
alim
bubt
bnjkjkjg
hhhhhhhhhhhhhhhjjjjjjjjjjjjjjhhhhhhhhhhhhhhh
yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy
kjghkfuwweuibmbvnvfgjgu
bbhh
Code: Select all
2
2
1
3
0
5
44
42
10
2
Give me six hours to chop down a tree and I will spend the first four sharpening the axe...(BUBT ILLUSION)
http://uhunt.felix-halim.net/id/155497
http://onlyprogramming.wordpress.com/
http://uhunt.felix-halim.net/id/155497
http://onlyprogramming.wordpress.com/
-
- New poster
- Posts: 4
- Joined: Tue Aug 18, 2015 9:52 am
Re: 11151 - Longest Palindrome
why am i getting wrong answer every time? check n help me plz.
#include<bits/stdc++.h>
using namespace std;
int a[1002][1002];
int main(){
int t, i, j, l;
char s[1005],r[1005];
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
scanf("%d\n", &t);
while(t--){
gets(s);
l = strlen(s);
if(l<1){printf("0\n");continue;}
j = 0;
for(i=l-1;i>=0;i--) r[j++] =s;
r[j] = '\0';
for(i=0;i<=l;i++){
a[0]=0;
}
for(j=0;j<=l;j++){
a[0][j]=0;
}
for(i=1;i<=l;i++){
for(j=1;j<=l;j++){
if(s[i-1]==r[j-1]){
a[j] = a[i-1][j-1]+1;
}
else if(a[i-1][j]>=a[j-1]){
a[j] = a[i-1][j];
}
else{
a[j] = a[j-1];
}
}
}
printf("%d\n", a[l][l]);
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int a[1002][1002];
int main(){
int t, i, j, l;
char s[1005],r[1005];
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
scanf("%d\n", &t);
while(t--){
gets(s);
l = strlen(s);
if(l<1){printf("0\n");continue;}
j = 0;
for(i=l-1;i>=0;i--) r[j++] =s;
r[j] = '\0';
for(i=0;i<=l;i++){
a[0]=0;
}
for(j=0;j<=l;j++){
a[0][j]=0;
}
for(i=1;i<=l;i++){
for(j=1;j<=l;j++){
if(s[i-1]==r[j-1]){
a[j] = a[i-1][j-1]+1;
}
else if(a[i-1][j]>=a[j-1]){
a[j] = a[i-1][j];
}
else{
a[j] = a[j-1];
}
}
}
printf("%d\n", a[l][l]);
}
return 0;
}
-
- New poster
- Posts: 16
- Joined: Fri Nov 15, 2013 9:33 pm
Re: 11151 - Longest Palindrome
The following code passed all the udebug test cases. But still getting WA. Please help
![:(](./images/smilies/icon_frown.gif)
![:(](./images/smilies/icon_frown.gif)
Code: Select all
Removed after AC