主题:[求助]===最长子串的问题LCS===
[问题描述]
序列Z=<B,C,D,B>是序列X=<A,B,C,B,D,A,B>的子序列,相应的递增下标序列为<2,3,5,7>。
一般地,给定一个序列X=<x1,x2,…,xm>,则另一个序列Z=<z1,z2,…,zk>是X的子序列,是指存在一个严格递增的下标序列〈i1,i2,…,ik〉使得对于所有j=1,2,…,k使Z中第j个元素zj与X中第ij个元素相同。
给定2个序列X和Y,当另一序列Z既是X的子序列又是Y的子序列时,称Z是序列X和Y的公共子序列。
你的任务是:给定2个序列X、Y,求X和Y的最长公共子序列Z。
[输入]
输入文件中的第1行是一个正整数T,(0<T<=10),表示有T组测试数据。接下来是每组测试数据的描述,每组测试数据有3行。
测试数据的第1行有2个正整数m、n,中间用一个空格隔开,(0<m,n<50);第2、3行是长度分别为m、n的2个序列X和Y,每个序列的元素间用一个空格隔开。序列中每个元素由字母、数字等构成。
输入直到文件结束。
[输出]
对输入中的每组测试数据,输出2行。先在一行上输出“Case #”,其中“#”是测试数据的组号(从1开始),再在第2行上输出这2个序列X、Y的最长公共子序列Z的长度。
[输入样例]
2
7 6
A B C B D A B
B D C A B A
8 9
b a a b a b a b
a b a b b a b b a
[输出样例]
Case 1
4
Case 2
6
下面是我的程序,编译通过,但输入数据的时候就不对了,比方说我输入:
2
3 2
A B C
然后按回车,就输出了:
2
2
还没让我输入第二个数组呢。。。
#include <iostream>
using namespace std;
void LCSLength(int m,int n,int *x,int *y,int **c) {
int i,j;
for(i=1;i<=m;i++) c[i][0]=0;
for(i=1;i<=n;i++) c[0][i]=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];
}
}
}
int main() {
int i,j;
int *x,*y;
int **c;
int count,num1,num2;
cin>>count;
for(i=0;i<count;i++) {
cin>>num1>>num2;
x=new int[num1+1];
for(j=1;j<=num1;j++)
cin>>x[j];
y=new int[num2+1];
for(j=1;j<=num2;j++)
cin>>y[j];
c=new int*[num1+1];
for(j=0;j<=num1;j++)
c[j]=new int[num2+1];
LCSLength(num1,num2,x,y,c);
cout<<c[num1][num2]<<endl;
delete[]x;
delete[]y;
delete[]c;
}
return 0;
}
谢谢各位大大帮忙!
序列Z=<B,C,D,B>是序列X=<A,B,C,B,D,A,B>的子序列,相应的递增下标序列为<2,3,5,7>。
一般地,给定一个序列X=<x1,x2,…,xm>,则另一个序列Z=<z1,z2,…,zk>是X的子序列,是指存在一个严格递增的下标序列〈i1,i2,…,ik〉使得对于所有j=1,2,…,k使Z中第j个元素zj与X中第ij个元素相同。
给定2个序列X和Y,当另一序列Z既是X的子序列又是Y的子序列时,称Z是序列X和Y的公共子序列。
你的任务是:给定2个序列X、Y,求X和Y的最长公共子序列Z。
[输入]
输入文件中的第1行是一个正整数T,(0<T<=10),表示有T组测试数据。接下来是每组测试数据的描述,每组测试数据有3行。
测试数据的第1行有2个正整数m、n,中间用一个空格隔开,(0<m,n<50);第2、3行是长度分别为m、n的2个序列X和Y,每个序列的元素间用一个空格隔开。序列中每个元素由字母、数字等构成。
输入直到文件结束。
[输出]
对输入中的每组测试数据,输出2行。先在一行上输出“Case #”,其中“#”是测试数据的组号(从1开始),再在第2行上输出这2个序列X、Y的最长公共子序列Z的长度。
[输入样例]
2
7 6
A B C B D A B
B D C A B A
8 9
b a a b a b a b
a b a b b a b b a
[输出样例]
Case 1
4
Case 2
6
下面是我的程序,编译通过,但输入数据的时候就不对了,比方说我输入:
2
3 2
A B C
然后按回车,就输出了:
2
2
还没让我输入第二个数组呢。。。
#include <iostream>
using namespace std;
void LCSLength(int m,int n,int *x,int *y,int **c) {
int i,j;
for(i=1;i<=m;i++) c[i][0]=0;
for(i=1;i<=n;i++) c[0][i]=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];
}
}
}
int main() {
int i,j;
int *x,*y;
int **c;
int count,num1,num2;
cin>>count;
for(i=0;i<count;i++) {
cin>>num1>>num2;
x=new int[num1+1];
for(j=1;j<=num1;j++)
cin>>x[j];
y=new int[num2+1];
for(j=1;j<=num2;j++)
cin>>y[j];
c=new int*[num1+1];
for(j=0;j<=num1;j++)
c[j]=new int[num2+1];
LCSLength(num1,num2,x,y,c);
cout<<c[num1][num2]<<endl;
delete[]x;
delete[]y;
delete[]c;
}
return 0;
}
谢谢各位大大帮忙!