10405 - Longest Common Subsequence
Moderator: Board moderators
10405 WA!
What's wrong?
Code: Select all
#include <stdio.h>
#include <string.h>
#define LEN 100
int m,n,i,j;
char c[LEN][LEN],b[LEN][LEN];
int ans;
char X[LEN],Y[LEN];
int LCS_length(){
m=strlen(X);
n=strlen(Y);
for(i=1;i<=m;i++) c[i][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]==Y[j]) {
c[i][j]=c[i-1][j-1]+1;
b[i][j]= 1;
}
else if(c[i-1][j]>=c[i][j-1]) {
c[i][j] = c[i-1][j];
b[i][j]=2;
}
else{
c[i][j]=c[i][j-1];
b[i][j]=3;
}
}
return c[m][n];
}
void main(){
while(1) {
gets(X);
if (feof(stdin)) break;
gets(Y);
ans = LCS_length();
printf("%d\n",ans);
}
}
fahim
#include <smile.h>
#include <smile.h>
-
- Experienced poster
- Posts: 106
- Joined: Thu Jan 29, 2004 12:07 pm
- Location: Bangladesh
- Contact:
10405 - Longest Common Subsequence
hi all...
i have submitted my code...
but! why WA ???
i dont really know the reason.. who anyone help me please...
the code is very simple LCS...
i have submitted my code...
but! why WA ???
i dont really know the reason.. who anyone help me please...
the code is very simple LCS...
Code: Select all
#include <stdio.h>
#include <string.h>
void main(void)
{
char str1[1010], str2[1010];
int len1, len2;
int i, j;
char map[1010][1010];
while ( 1 )
{
if ( gets(str1) == NULL )
break;
if ( gets(str2) == NULL )
break;
len1 = strlen(str1);
len2 = strlen(str2);
for ( i = 0 ; i <= len1 ; i++ )
map[i][0] = 0;
for ( i = 0 ; i <= len2 ; i++ )
map[0][i] = 0;
for ( i = 1 ; i <= len1 ; i++ )
for ( j = 1 ; j <= len2 ; j++ )
if ( str1[i-1] == str2[j-1] )
{
map[i][j] = map[i-1][j-1] + 1;
}
else if ( map[i-1][j] >= map[i][j-1] )
{
map[i][j] = map[i-1][j];
}
else
{
map[i][j] = map[i][j-1];
}
printf("%d\n", map[len1][len2]);
}
}
out of limit...
since the strings can be as many as 1000 characters it implies the result could have a value of 1000..
.. so, char map[1010][1010] won't work.
try converting the data type to integer.
.. so, char map[1010][1010] won't work.
try converting the data type to integer.
10405, WA, plz HELP!!!
getting WA...
here is my code...
//10405 - Longest Common Subsequence
#include<stdio.h>
#include<string.h>
char b[1001][1001],c[1001][1001];
char x[1005],y[1005];
void lcs(int m,int n)
{
int i,j;
for(i=1;i<m+1;i++){
c[0]=0;
b[0]=' ';
}
for(j=0;j<m+1;j++){
c[0][j]=0;
b[0][j]=' ';
}
for(i=1;i<m+1;i++){
for(j=1;j<n+1;j++){
if(x==y[j]){
c[j]=c[i-1][j-1]+1;
b[j]='C';
}
else if(c[i-1][j]>=c[j-1]){
c[j]=c[i-1][j];
b[j]='U';
}
else{
c[j]=c[j-1];
b[i][j]='L';
}
}
}
}
void main()
{
int m,n;
//freopen("E:\\test.txt","rt",stdin);
while(gets(&x[1]) != NULL && gets(&y[1]) != NULL){
m = strlen(&x[1]);
n = strlen(&y[1]);
lcs(m,n);
printf("%d\n",c[m][n]);
}
}
here is my code...
//10405 - Longest Common Subsequence
#include<stdio.h>
#include<string.h>
char b[1001][1001],c[1001][1001];
char x[1005],y[1005];
void lcs(int m,int n)
{
int i,j;
for(i=1;i<m+1;i++){
c[0]=0;
b[0]=' ';
}
for(j=0;j<m+1;j++){
c[0][j]=0;
b[0][j]=' ';
}
for(i=1;i<m+1;i++){
for(j=1;j<n+1;j++){
if(x==y[j]){
c[j]=c[i-1][j-1]+1;
b[j]='C';
}
else if(c[i-1][j]>=c[j-1]){
c[j]=c[i-1][j];
b[j]='U';
}
else{
c[j]=c[j-1];
b[i][j]='L';
}
}
}
}
void main()
{
int m,n;
//freopen("E:\\test.txt","rt",stdin);
while(gets(&x[1]) != NULL && gets(&y[1]) != NULL){
m = strlen(&x[1]);
n = strlen(&y[1]);
lcs(m,n);
printf("%d\n",c[m][n]);
}
}
Darkness be my guide...
-
- Learning poster
- Posts: 57
- Joined: Fri Oct 10, 2003 11:01 pm
- Location: in front of PC
- Contact:
hello
hello
here is an ACC soln
it's simple...
isn't it???????
again...
USE proper formet while posting code.
ur's is not better readable, let alone to bebug.
and i will remove the code as u reply me..
bye!!!!![:lol:](./images/smilies/icon_lol.gif)
here is an ACC soln
Code: Select all
#include <stdio.h>
#include <string.h>
const int MAX = 1005;
char x[MAX]={'a'}, y[MAX]={'a'};
int c[MAX][MAX];
void LCS_Length(){
int m = strlen(x)-1, n = strlen(y)-1, i,j;
for(i = 1; i<=m; i++) c[i][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] == y[j] ){
c[i][j] = c[i-1][j-1] + 1;
}
else if( c[i-1][j] >= c[i][j-1] ){
c[i][j] = c[i-1][j];
}
else
c[i][j] = c[i][j-1];
}
}
printf("%d\n", c[m][n]);
}
void main(void){
//freopen("f:\\10405.txt","rb",stdin);
while( gets(x+1)&& gets(y+1) ){
LCS_Length();
}
}
isn't it???????
again...
USE proper formet while posting code.
ur's is not better readable, let alone to bebug.
and i will remove the code as u reply me..
bye!!!!
![:lol:](./images/smilies/icon_lol.gif)
There are two tragedies in life one is to lose your hearts' desire and another is to gain it --- GBS.
-
- A great helper
- Posts: 481
- Joined: Sun Jun 19, 2005 1:18 am
- Location: European Union (Slovak Republic)
Re: 10405, WA, plz HELP!!!
There should be n+1 in the second for loop.Darken wrote:Code: Select all
for(i=1;i<m+1;i++){ c[i][0]=0; b[i][0]=' '; } for(j=0;j<m+1;j++){ c[0][j]=0; b[0][j]=' '; }
10405 WA,help
I use dynamic programming, but I still get WA, can someone help me.
#include <string>
#include <cstdlib>
#include <vector>
#include <iostream>
using namespace std;
#define MAX(a, b) ((a)>(b)?(a):(b))
#define MIN(a, b) ((a)>(b)?(a):(b))
class LCSLength
{
public:
LCSLength(){}
string solve(string A, string B);
int length(string A, string B);
};
int LCSLength::length(string A, string B)
{
if(A.size()==0 || B.size()==0) return 0;
int m = A.size()+1;
int n = B.size()+1;
int* c = new int[m*n];
memset(c,0,m*n*sizeof(int));
c[0] = 0;
int i,j;
for(i=1;i<m;i++){
for(j=1;j<n;j++){
if(A[i-1] == B[j-1]){
c[i*n+j] = c[(i-1)*n+(j-1)]+1;
}else{
c[i*n+j] = MAX(c[i*n+j-1],c[(i-1)*n+j]);
}
//cout<<c[i*n+j]<<" ";
}
//cout<<endl;
}
int ret = c[m*n-1];
delete[] c;
return ret;
}
string LCSLength::solve(string A, string B)
{
int M = A.size();
int N = B.size();
if(M==0 || N==0) return "";
string *str = new string[M*N];
if(A[0] == B[0]) str[0] = A[0];
else str[0] = "";
int i,j;
for(i=0;i<M;i++){
for(j=0;j<N;j++){
if(i==0 && j==0) continue;
if(A == B[j]){
if(i==0 || j==0){
str[i*N+j] = A;
}else{
str[i*N+j] = str[(i-1)*N+(j-1)] + A;
}
//cout<<str[i*N+j]<<endl;
}
else{
if(i==0){ str[i*N+j] = str[i*N+j-1]; continue; }
if(j==0){ str[i*N+j] = str[(i-1)*N+j]; continue; }
if(str[(i-1)*N+j].size() >= str[i*N+j-1].size())
str[i*N+j] = str[(i-1)*N+j];
else str[i*N+j] = str[i*N+j-1];
}
}
}
return str[M*N-1];
}
int main()
{
string A,B;
LCSLength LCS;
while(cin>>A>>B){
cout<<LCS.length(A,B)<<endl;
}
return 0;
}[/code]
#include <string>
#include <cstdlib>
#include <vector>
#include <iostream>
using namespace std;
#define MAX(a, b) ((a)>(b)?(a):(b))
#define MIN(a, b) ((a)>(b)?(a):(b))
class LCSLength
{
public:
LCSLength(){}
string solve(string A, string B);
int length(string A, string B);
};
int LCSLength::length(string A, string B)
{
if(A.size()==0 || B.size()==0) return 0;
int m = A.size()+1;
int n = B.size()+1;
int* c = new int[m*n];
memset(c,0,m*n*sizeof(int));
c[0] = 0;
int i,j;
for(i=1;i<m;i++){
for(j=1;j<n;j++){
if(A[i-1] == B[j-1]){
c[i*n+j] = c[(i-1)*n+(j-1)]+1;
}else{
c[i*n+j] = MAX(c[i*n+j-1],c[(i-1)*n+j]);
}
//cout<<c[i*n+j]<<" ";
}
//cout<<endl;
}
int ret = c[m*n-1];
delete[] c;
return ret;
}
string LCSLength::solve(string A, string B)
{
int M = A.size();
int N = B.size();
if(M==0 || N==0) return "";
string *str = new string[M*N];
if(A[0] == B[0]) str[0] = A[0];
else str[0] = "";
int i,j;
for(i=0;i<M;i++){
for(j=0;j<N;j++){
if(i==0 && j==0) continue;
if(A == B[j]){
if(i==0 || j==0){
str[i*N+j] = A;
}else{
str[i*N+j] = str[(i-1)*N+(j-1)] + A;
}
//cout<<str[i*N+j]<<endl;
}
else{
if(i==0){ str[i*N+j] = str[i*N+j-1]; continue; }
if(j==0){ str[i*N+j] = str[(i-1)*N+j]; continue; }
if(str[(i-1)*N+j].size() >= str[i*N+j-1].size())
str[i*N+j] = str[(i-1)*N+j];
else str[i*N+j] = str[i*N+j-1];
}
}
}
return str[M*N-1];
}
int main()
{
string A,B;
LCSLength LCS;
while(cin>>A>>B){
cout<<LCS.length(A,B)<<endl;
}
return 0;
}[/code]
Sorry, I make a mistake
But I only use MAX in program
-
- Learning poster
- Posts: 99
- Joined: Sun Apr 06, 2003 5:53 am
- Location: Dhaka, Bangladesh
- Contact:
Try taking the input with gets() or similar functions. I think there can be whitespaces within the strings. Otherwise the class LCSLength seems ok.
And please, next time u post codes in the board, try removing unnecessary portions of the code. This will save time of people who are trying to help you. You have a complete function in your code which is never called
, let alone a single macro . ![:-?](./images/smilies/icon_confused.gif)
And please, next time u post codes in the board, try removing unnecessary portions of the code. This will save time of people who are trying to help you. You have a complete function in your code which is never called
![:roll:](./images/smilies/icon_rolleyes.gif)
![:-?](./images/smilies/icon_confused.gif)
Where's the "Any" key?