博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
LCS记录
阅读量:6284 次
发布时间:2019-06-22

本文共 1148 字,大约阅读时间需要 3 分钟。

  如题:求两个序列的最长公共序列。(如:“ABCBDAB”与“BCDB”最长公共序列为"BCDB")代码如下:

#define MAX_SIZE 200char a[MAX_SIZE], b[MAX_SIZE], str[MAX_SIZE];int num[MAX_SIZE][MAX_SIZE];//计算最优值,即最长公用字符串的长度int lcs_len(int a_length, int b_length){    int t, s;    if (a_length == 0 || b_length == 0)        num[a_length][b_length] = 0;    else if (a[a_length - 1] == b[b_length - 1])        num[a_length][b_length] = lcs_len(a_length - 1, b_length - 1) + 1;    else    {        t = lcs_len(a_length, b_length - 1);        s = lcs_len(a_length - 1, b_length);        if (t > s)            num[a_length][b_length] = t;        else            num[a_length][b_length] = s;    }    return num[a_length][b_length];}//找出字符串(注意:此方法只能找出字符串中的一种)void lcs_str(int str_len, int a_len, int b_len){    if ((!a_len) || (!b_len))        return;    if (num[a_len][b_len] == num[a_len - 1][b_len])        lcs_str(str_len, a_len - 1, b_len);    else if (num[a_len][b_len] == num[a_len][b_len - 1])        lcs_str(str_len, a_len, b_len - 1);    else    {        str[str_len - 1] = a[a_len - 1];        lcs_str(str_len - 1, a_len - 1, b_len - 1);    }}

仅供学习记录。

转载于:https://www.cnblogs.com/czx1/p/6033112.html

你可能感兴趣的文章
重叠(Overlapped)IO模型
查看>>
Git使用教程
查看>>
使用shell脚本自动监控后台进程,并能自动重启
查看>>
Flex&Bison手册
查看>>
solrCloud+tomcat+zookeeper集群配置
查看>>
/etc/fstab,/etc/mtab,和 /proc/mounts
查看>>
Apache kafka 简介
查看>>
socket通信Demo
查看>>
技术人员的焦虑
查看>>
js 判断整数
查看>>
mongodb $exists
查看>>
js实现页面跳转的几种方式
查看>>
sbt笔记一 hello-sbt
查看>>
常用链接
查看>>
pitfall override private method
查看>>
!important 和 * ----hack
查看>>
聊天界面图文混排
查看>>
控件的拖动
查看>>
svn eclipse unable to load default svn client的解决办法
查看>>
Android.mk 文件语法详解
查看>>