c++语言写最长公共子序列问题
需积分: 38 48 浏览量
2018-07-07
00:40:02
上传
评论 1
收藏 36KB DOC 举报
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
using namespace std;
int lcs(char A[], char B[], char C[], int n, int m)
{
int i, j, k, len;
//int(*L)[m + 1] = new int[n + 1][m + 1];
//int(*s)[m + 1] = new int[n + 1][m + 1];
int **L = new int*[n + 1]; //搜索过程中的子序列长度
int **s = new int*[n + 1]; //搜索过程中的子序列状态
for (i = 0; i <= n; i++)
{
L[i] = new int[m + 1];
s[i] = new int[m + 1];
}
for (i = 0; i <= n; i++)
L[i][0] = 0;
for (i = 0; i <= m; i++)
L[0][i] = 0;
for (i = 1; i <= n; i++)
{
for (j = 1; j <= m; j++)
{
if (A[i] == B[j])
{
L[i][j] = L[i - 1][j - 1] + 1;
s[i][j] = 1;
}
else if (L[i - 1][j] >= L[i][j - 1])
{
L[i][j] = L[i - 1][j];
s[i][j] = 2;
}
else
评论0
最新资源