博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
最长公共子序列---动态规划
阅读量:5833 次
发布时间:2019-06-18

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

一: 作用

       最长公共子序列的问题常用于解决字符串的相似度,是一个非常实用的算法,作为码农,此算法是我们的必备基本功。

二:概念

     举个例子,cnblogs这个字符串中子序列有多少个呢?很显然有27个,比如其中的cb,cgs等等都是其子序列,我们可以看出

子序列不见得一定是连续的,连续的那是子串。

     我想大家已经了解了子序列的概念,那现在可以延伸到两个字符串了,那么大家能够看出:cnblogs和belong的公共子序列吗?

在你找出的公共子序列中,你能找出最长的公共子序列吗?

从图中我们看到了最长公共子序列为blog,仔细想想我们可以发现其实最长公共子序列的个数不是唯一的,可能会有两个以上,

但是长度一定是唯一的,比如这里的最长公共子序列的长度为4。

 

三:解决方案

<1> 枚举法

       这种方法是最简单,也是最容易想到的,当然时间复杂度也是龟速的,我们可以分析一下,刚才也说过了cnblogs的子序列

个数有27个 ,延伸一下:一个长度为N的字符串,其子序列有2N个,每个子序列要在第二个长度为N的字符串中去匹配,匹配一次

需要O(N)的时间,总共也就是O(N*2N),可以看出,时间复杂度为指数级,恐怖的令人窒息。

 

<2> 动态规划

      既然是经典的题目肯定是有优化空间的,并且解题方式是有固定流程的,这里我们采用的是矩阵实现,也就是二维数组。

第一步:先计算最长公共子序列的长度。

第二步:根据长度,然后通过回溯求出最长公共子序列。

现有两个序列X={x1,x2,x3,...xi},Y={y1,y2,y3,....,yi},

设一个C[i,j]: 保存Xi与Yj的LCS的长度。

递推方程为:

代码

1 package digui_fenzhi; 2  3 public class LCSProblem{ 4     public static void main(String[] args){ 5         String[] x = {"", "A", "B", "C", "B", "D", "A", "B"}; 6         String[] y = {"", "B", "D", "C", "A", "B", "A"}; 7         int[][] b = getLength(x, y); 8         Display(b, x, x.length-1, y.length-1); 9     }10     public static int[][] getLength(String[] x, String[] y){11         int[][] b = new int[x.length][y.length];12         int[][] c = new int[x.length][y.length];13         for(int i=1; i
= c[i][j-1]){19 c[i][j] = c[i-1][j];20 b[i][j] = 0;21 }else{22 c[i][j] = c[i][j-1];23 b[i][j] = -1;24 }25 }26 }27 return b;28 }29 public static void Display(int[][] b, String[] x, int i, int j){30 if(i == 0 || j == 0)31 return;32 if(b[i][j] == 1){33 Display(b, x, i-1, j-1);34 System.out.print(x[i] + " ");35 }36 else if(b[i][j] == 0){37 Display(b, x, i-1, j);38 }39 else if(b[i][j] == -1){40 Display(b, x, i, j-1);41 }42 }43 }

 

转载于:https://www.cnblogs.com/yijiesuifeng/p/3789866.html

你可能感兴趣的文章
甘肃发首版《3D打印职业教育教材》:校企合作育专才
查看>>
李娜入选国际网球名人堂 成亚洲第一人
查看>>
为找好心人抚养孩子 浙江一离婚父亲将幼童丢弃公园
查看>>
晚婚晚育 近20年巴西35岁以上孕妇增加65%
查看>>
读书:为了那个美妙的咔哒声
查看>>
jsp改造之sitemesh注意事项
查看>>
智能硬件的时代,嵌入式是否已经日薄西山
查看>>
SpringBoot-Shiro使用
查看>>
iOS 9.0之后NSString encode方法替换
查看>>
解决 ThinkPHP5 无法接收 客户端 Post 传递的 Json 参数
查看>>
ASMFD (ASM Filter Driver) Support on OS Platforms (Certification Matrix). (文档 ID 2034681.1)
查看>>
CRM Transaction处理中的权限控制
查看>>
[转]linux创建链接文件的两种方法
查看>>
python ipaddress模块使用
查看>>
文件权限
查看>>
busybox里的僵尸进程为何那么多
查看>>
python debug
查看>>
java 连接数据库之一个完整的函数
查看>>
mysql脚本
查看>>
OllyDBG 入门系列教学--让你瞬间成为破解高手
查看>>