网站设计方案范本,建设工程施工合同的特点,做网站相册,网站整站源码下载工具一、作用
最长公共子序列的问题常用于解决字符串的相似度#xff0c;是一个非常实用的算法#xff0c;作为码农#xff0c;此算法是我们的必备基本功。
二、概念
举个例子#xff0c;cnblogs 这个字符串中子序列有多少个呢#xff1f;很显然有 27 个#xff0c;比如其…一、作用
最长公共子序列的问题常用于解决字符串的相似度是一个非常实用的算法作为码农此算法是我们的必备基本功。
二、概念
举个例子cnblogs 这个字符串中子序列有多少个呢很显然有 27 个比如其中的 cb,cgs 等等都是其子序列我们可以看出子序列不见得一定是连续的连续的那是子串。 我想大家已经了解了子序列的概念那现在可以延伸到两个字符串了那么大家能够看出cnblogs 和 belong 的公共子序列吗 在你找出的公共子序列中你能找出最长的公共子序列吗
三、解决方案
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 的长度。 递推方程为 不知道大家看懂了没动态规划的一个重要性质特点就是解决“子问题重叠”的场景可以有效的避免重复计算根据上面的公式其实可以发现 C[i,j]一直保存着当前(Xi,Yi)的最大子序列长度。 using System;namespace ConsoleApplication2{public class Program{static int[,] martix;static string str1 cnblogs;static string str2 belong;static void Main(string[] args){martix new int[str1.Length 1, str2.Length 1];LCS(str1, str2);//只要拿出矩阵最后一个位置的数字即可Console.WriteLine(当前最大公共子序列的长度为:{0}, martix[str1.Length, str2.Length]);Console.Read();}static void LCS(string str1, string str2){//初始化边界过滤掉0的情况for (int i 0; i str1.Length; i)martix[i, 0] 0;for (int j 0; j str2.Length; j)martix[0, j] 0;//填充矩阵for (int i 1; i str1.Length; i){for (int j 1; j str2.Length; j){//相等的情况if (str1[i - 1] str2[j - 1]){martix[i, j] martix[i - 1, j - 1] 1;}else{//比较“左边”和“上边“根据其max来填充if (martix[i - 1, j] martix[i, j - 1])martix[i, j] martix[i - 1, j];elsemartix[i, j] martix[i, j - 1];}}}}}}图大家可以自己画一画代码完全是根据上面的公式照搬过来的长度的问题我们已经解决了这次要解决输出最长子序列的问题我们采用一个标记函数 Flag[i,j]当 ①C[i,j]C[i-1,j-1]1 时 标记 Flag[i,j]“left_up”; 左上方箭头 ②C[i-1,j]C[i,j-1] 时 标记 Flag[i,j]“left”; 左箭头 ③: C[i-1,j]C[i,j-1] 时 标记 Flag[i,j]“up”; 上箭头 例如我输入两个序列 XacgbfhkYcegefkh。 using System;namespace ConsoleApplication2{public class Program{static int[,] martix;static string[,] flag;static string str1 acgbfhk;static string str2 cegefkh;static void Main(string[] args){martix new int[str1.Length 1, str2.Length 1];flag new string[str1.Length 1, str2.Length 1];LCS(str1, str2);//打印子序列SubSequence(str1.Length, str2.Length);Console.Read();}static void LCS(string str1, string str2){//初始化边界过滤掉0的情况for (int i 0; i str1.Length; i)martix[i, 0] 0;for (int j 0; j str2.Length; j)martix[0, j] 0;//填充矩阵for (int i 1; i str1.Length; i){for (int j 1; j str2.Length; j){//相等的情况if (str1[i - 1] str2[j - 1]){martix[i, j] martix[i - 1, j - 1] 1;flag[i, j] left_up;}else{//比较“左边”和“上边“根据其max来填充if (martix[i - 1, j] martix[i, j - 1]){martix[i, j] martix[i - 1, j];flag[i, j] left;}else{martix[i, j] martix[i, j - 1];flag[i, j] up;}}}}}static void SubSequence(int i, int j){if (i 0 || j 0)return;if (flag[i, j] left_up){Console.WriteLine({0}: 当前坐标:{1},{2}, str2[j - 1], i - 1, j - 1);//左前方SubSequence(i - 1, j - 1);}else{if (flag[i, j] up){SubSequence(i, j - 1);}else{SubSequence(i - 1, j);}}}}}好我们再输入两个字符串
static string str1 abcbdab;
static string str2 bdcaba;通过上面的两张图我们来分析下它的时间复杂度和空间复杂度。 **时间复杂度**构建矩阵我们花费了 O(MN)的时间回溯时我们花费了 OMN)的时间两者相加最终我们花费了 O(MN)的时间。 **空间复杂度**构建矩阵我们花费了 O(MN)的空间标记函数也花费了 O(MN)的空间两者相加最终我们花费了 O(MN)的空间。
