10405 - Longest Common Subsequence

All about problems in Volume 104. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

sklitzz
New poster
Posts: 32
Joined: Fri Dec 03, 2004 5:19 pm

Post by sklitzz » Fri Feb 18, 2005 9:44 am

Thanks Larry I got AC

User avatar
smilitude
Experienced poster
Posts: 137
Joined: Fri Jul 01, 2005 12:21 am

10405 WA!

Post by smilitude » Fri Jul 01, 2005 12:37 am

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>

Sanny
Learning poster
Posts: 78
Joined: Sat Feb 14, 2004 3:59 pm
Location: BUET
Contact:

Post by Sanny » Fri Jul 01, 2005 8:11 am

String lengths can be as much as 1000.

Regards
Sanny

Raiyan Kamal
Experienced poster
Posts: 106
Joined: Thu Jan 29, 2004 12:07 pm
Location: Bangladesh
Contact:

Post by Raiyan Kamal » Fri Jul 15, 2005 9:36 pm

Why do you need the b[][] array ? The problem does not ask you to print LCS, just print the length of the LCS.

pipo
New poster
Posts: 47
Joined: Tue May 11, 2004 6:43 pm
Location: Republic of Korea

10405 - Longest Common Subsequence

Post by pipo » Wed Jul 20, 2005 7:42 pm

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...

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]);
	}	
}

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

out of limit...

Post by sohel » Thu Jul 21, 2005 8:28 am

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.

pipo
New poster
Posts: 47
Joined: Tue May 11, 2004 6:43 pm
Location: Republic of Korea

Post by pipo » Thu Jul 21, 2005 9:40 am

sohel!! thank you very much...

you're right...

i didn't think about that point...

I just converted the data type to integer... and then I finally got AC..

thanks a lot :P ...

Darken
New poster
Posts: 2
Joined: Thu Sep 08, 2005 8:08 pm

10405, WA, plz HELP!!!

Post by Darken » Thu Sep 08, 2005 9:10 pm

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]);
}
}
Darkness be my guide...

I LIKE GN
Learning poster
Posts: 57
Joined: Fri Oct 10, 2003 11:01 pm
Location: in front of PC
Contact:

hello

Post by I LIKE GN » Fri Sep 09, 2005 3:59 pm

hello
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();
	}
}

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:
There are two tragedies in life one is to lose your hearts' desire and another is to gain it --- GBS.

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Re: 10405, WA, plz HELP!!!

Post by Martin Macko » Sat Sep 10, 2005 8:51 am

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]=' ';
	}
There should be n+1 in the second for loop.

Darken
New poster
Posts: 2
Joined: Thu Sep 08, 2005 8:08 pm

Thanx...

Post by Darken » Fri Sep 16, 2005 4:18 pm

it was not the problem... I didn't take the inputs for a blank line... any way finally i have got acceptance:P . thanx for ur care. take care. bye.
Darkness be my guide...

xlvector
New poster
Posts: 11
Joined: Thu Dec 29, 2005 8:30 am
Contact:

10405 WA,help

Post by xlvector » Mon Jan 02, 2006 8:35 am

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]

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

Post by mamun » Mon Jan 02, 2006 4:53 pm

What's the difference between your MAX and MIN macros? :P

xlvector
New poster
Posts: 11
Joined: Thu Dec 29, 2005 8:30 am
Contact:

Sorry, I make a mistake

Post by xlvector » Tue Jan 03, 2006 3:57 am

But I only use MAX in program

Solaris
Learning poster
Posts: 99
Joined: Sun Apr 06, 2003 5:53 am
Location: Dhaka, Bangladesh
Contact:

Post by Solaris » Tue Jan 03, 2006 8:42 am

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 :roll: , let alone a single macro . :-?
Where's the "Any" key?

Post Reply

Return to “Volume 104 (10400-10499)”