回 帖 发 新 帖 刷新版面

主题:[求助]===最长子串的问题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;
}

谢谢各位大大帮忙!

回复列表 (共1个回复)

沙发

能帮忙看看哪里出错了吗?谢谢

我来回复

您尚未登录,请登录后再回复。点此登录或注册