“最长公共字符串子序列”问题的动态规划法算法.pdf
版权申诉
26 浏览量
2022-07-09
17:11:24
上传
评论
收藏 200KB PDF 举报
“最长公共字符串子序列”问题的动态规划法算法
/*
标题：<<系统设计师>>应试编程实例-[动态规划算法程序设计]
作者：成晓旭
时间：2002 年 09 月 15 日(18:20:00-21:25:00)
实现“最长公共字符串子序列”问题的动态规划算法实现函数
时间：2002 年 09 月 15 日(21:31:00-22:00:00)
实现“最长公共字符串子序列”问题的动态规划算法实现函数
*/
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#define MAXN 64 //全局最大值常量
//:=========================“ 最 长 公 共 字 符 串 子 序 列 ” 问 题 的 动 态 规 划 法 算 法
=========================
//计算两个字符串序列的最长公共子序列的长度函数
int First_Born_SubStr_Len(char *a,char *b,int substrlen[][MAXN])
{
int i,j,m = strlen(a),n = strlen(b);
for(i = 0;i <= m;i++)
substrlen[i][0] = 0;
for(j = 1;j <= m;j++)
substrlen[0][j] = 0;
for(i = 1;i <= m;i++)
{
for(j = 1;j <= n;j++)
if(a[i - 1] == b[j - 1])
substrlen[i][j] = substrlen[i - 1][j - 1] + 1;
else if(substrlen[i - 1][j] >= substrlen[i][j - 1])
substrlen[i][j] = substrlen[i - 1][j];
else
substrlen[i][j] = substrlen[i][j - 1];
}
return(substrlen[m][n]);
}
//构造最长公共子序列函数
char *Build_First_Born_SubStr(char *a,char *b,char str[])
{
int k,i = strlen(a),j = strlen(b),array[MAXN][MAXN];
k = First_Born_SubStr_Len(a,b,array);
str[k] = '';
while(k > 0)
资源评论
