按照书上的算法写的代码，但是结果总是不对，求大神帮忙看一下
#include <stdlib.h>
#include <string.h>

#define OK 1
#define Error 0
#define OVERFLOW -2
#define INFEASIBLE -1
#define TURE 1
#define FALSE 0


typedef int Status;
typedef int SElemtype;


#define ATACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define OPTR 10
#define OPND 10
Status lcs(char A[],char B[]);


#endif // LCS_H_INCLUDED

Status lcs(char A[],char B[])
{
    int i,j,L[20][20],m,n;
      n=strlen(A);
      m=strlen(B);
    for(i=0;i<n;i++)
        L[i][0]=0;
    for(j=0;j<m;j++)
        L[0][j]=0;
    for(i=1;i<=n;i++)

   {
       for(j=1;i<=m;j++)
        if('A[i]'=='B[j]')
            L[i][j]=L[i-1][j-1]+1;
         else
            {
                if(L[i][j-1]>L[i-1][j])
                  L[i][j]=L[i][j-1];
             else L[i][j]=L[i-1][j];
         }
   }
       return L[n][m];

}
#include <iostream>
#include"LCS.h"
#include <string.h>

using namespace std;

int main()
{

    char A[20],B[20];
    int i,n,m,MAX;
    printf("请输入一个字符串A:");
      gets(A);
    printf("请输入一个字符串B:");
      gets(B);
    MAX=lcs(A,B);
    printf("最长公共子序列的长度为：%d",lcs(A,B));

}

我的理解是子串应是相同字母或数字在一起才是子串，否则不是，如ab是abcd,cdab,vfgabdd的子串，而不是acdb的子串．

#include<stdio.h>
#include<string.h>
char ls[10];
void lcs(char a[],char b[]);
int main() {
    char a[10],b[10];
    gets(a);
    gets(b);
    lcs(a,b);
    return 0;
}
void lcs(char a[],char b[]) {
    int t=0,flag=0,i,j;
    for( i=0; i<strlen(a); i++) {
        for( j=0; j<strlen(b); j++)
            while(a[i]==b[j]) {
                ls[t]=a[i];
                t++;
                i++;
                j++;
                flag=1;
            }
        if(flag)
            break;
    }
    ls[t]='\0';
    printf("%d",strlen(ls));
}

然而你的理解没什么用
这个题目里面
ab 的确是 acdfssfsb的子串

谢谢啦，我刚才找到问题在哪了
把 if('A[i]'=='B[j]')
改成 if(A[i]==B[j])就行了

lcs算法~
如果只是输出长度用一维数组就可以了吧~
二维应该是方便回溯输出具体组成的~
看到优化后用一维数组用回溯也能回溯,不过回溯后的是反方向的,要重新倒过来一次才进行输出,就是代码变得长了


for(j=1;i<=m;j++)
        if('A[i]'=='B[j]')
            L[i][j]=L[i-1][j-1]+1;
         else
            {
                if(L[i][j-1]>L[i-1][j])
                  L[i][j]=L[i][j-1];
             else L[i][j]=L[i-1][j];
         }

从这段代码可以看出,对于二维数组L的状态更新的第一维取值只和i和i-1的值有关~
也就意味着在i-1前面的数据已经用不到了,固可以覆盖处理(在动态规划上也叫用滚动数组来优化空间)

其实,这段代码的意思就是说用一个数组记录当前最大匹配长度,每个位置对应其主串对应字符的位置~
如果只是获取其最大长度,则具体流程具体流程是~


1:先对标记数组初始化为0

2:对子串和主串的第i个字符进行一个一个字符检测~

3:如果子串字符和主串相等,并大于等于其当前值的情况下,那就把当前值+1
否则原来的值等于其前一个下标的值~

4:i自增1后,判断是否遍历完主串,如果没有则跳会到第二步,否则结束循环~

5:返回标记数组最后一个元素(标记数组总是非递减的,也就意味着最后一个元素必然是最大的)


为了方便处理,顾及到可能会出现j-1<0的情况,标记数组通常下标从1开始且mark[0]=0;

大概就是这样~

[此贴子已经被作者于2018-5-18 04:51编辑过]