## 10405 - Longest Common Subsequence

Moderator: Board moderators

sklitzz
New poster
Posts: 32
Joined: Fri Dec 03, 2004 5:19 pm
Thanks Larry I got AC

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

### 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;
for(j=0;j<=n;j++) c[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:
String lengths can be as much as 1000.

Regards
Sanny

Raiyan Kamal
Experienced poster
Posts: 106
Joined: Thu Jan 29, 2004 12:07 pm
Contact:
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

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, str2;
int len1, len2;
int i, j;
char map;

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;
for ( i = 0 ; i <= len2 ; i++ )
map[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]);
}
}
``````

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

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

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

### 10405, WA, plz HELP!!!

getting WA...
here is my code...
//10405 - Longest Common Subsequence

#include<stdio.h>
#include<string.h>

char b,c;
char x,y;

void lcs(int m,int n)
{
int i,j;

for(i=1;i<m+1;i++){
c=0;
b=' ';
}
for(j=0;j<m+1;j++){
c[j]=0;
b[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) != NULL && gets(&y) != NULL){
m = strlen(&x);
n = strlen(&y);

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

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;

for(j = 0; j<=n; j++) c[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!!!! There are two tragedies in life one is to lose your hearts' desire and another is to gain it --- GBS.

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

Darken wrote:

Code: Select all

``````	for(i=1;i<m+1;i++){
c[i]=0;
b[i]=' ';
}
for(j=0;j<m+1;j++){
c[j]=0;
b[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...

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

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;
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 == B) str = A;
else str = "";
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
Contact:
What's the difference between your MAX and MIN macros? xlvector
New poster
Posts: 11
Joined: Thu Dec 29, 2005 8:30 am
Contact:

### Sorry, I make a mistake

But I only use MAX in program

Solaris
Learning poster
Posts: 99
Joined: Sun Apr 06, 2003 5:53 am
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 . 