热门标签 | HotTags
当前位置:  开发笔记 > 人工智能 > 正文

利用C++实现最长公共子序列与最长公共子串

这篇文章主要给大家介绍了如何利用C++实现最长公共子序列与最长公共子串,文章一开始就给大家简单的介绍了什么是子序列,子串应该比较好理解就不用多介绍了,人后通过算法及示例代码详细介绍了C++实现的方法,有需要的朋友们可以参考借鉴,下面来一起看看吧。

一、问题描述

子串应该比较好理解,至于什么是子序列,这里给出一个例子:有两个母串

cnblogs

belong

比如序列bo, bg, lg在母串cnblogs与belong中都出现过并且出现顺序与母串保持一致,我们将其称为公共子序列。最长公共子序列(Longest Common Subsequence, LCS),顾名思义,是指在所有的子序列中最长的那一个。子串是要求更严格的一种子序列,要求在母串中连续地出现。在上述例子的中,最长公共子序列为blog(cnblogs, belong),最长公共子串为lo(cnblogs, belong)。

二、求解算法

对于母串X=X=, Y=Y= ,求LCS与最长公共子串。

暴力解法

假设 m, 对于母串XX,我们可以暴力找出2m2m个子序列,然后依次在母串YY中匹配,算法的时间复杂度会达到指数级O(n∗2m)O(n∗2m) 。显然,暴力求解不太适用于此类问题。

动态规划

假设Z=Z=是XX与YY的LCS, 我们观察到

     如果xm=ynxm=yn,则zk=xm=ynzk=xm=yn,有Zk−1Zk−1是Xm−1Xm−1与Yn−1Yn−1的LCS;

     如果xm≠ynxm≠yn,则ZkZk是XmXm与Yn−1Yn−1的LCS,或者是Xm−1Xm−1与YnYn的LCS。

因此,求解LCS的问题则变成递归求解的两个子问题。但是,上述的递归求解的办法中,重复的子问题多,效率低下。改进的办法——用空间换时间,用数组保存中间状态,方便后面的计算。这就是动态规划(DP)的核心思想了。

DP 求解 LCS

用二维数组c[i][j]记录串x1x2⋯xix1x2⋯xi与y1y2⋯yjy1y2⋯yj的LCS长度,则可得到状态转移方程

代码实现

public static int lcs(String str1, String str2) {
 int len1 = str1.length();
 int len2 = str2.length();
 int c[][] = new int[len1+1][len2+1];
 for (int i = 0; i <= len1; i++) {
 for( int j = 0; j <= len2; j++) {
  if(i == 0 || j == 0) {
  c[i][j] = 0;
  } else if (str1.charAt(i-1) == str2.charAt(j-1)) {
  c[i][j] = c[i-1][j-1] + 1;
  } else {
  c[i][j] = max(c[i - 1][j], c[i][j - 1]);
  }
 }
 }
 return c[len1][len2];
}

DP 求解最长公共子串

前面提到了子串是一种特殊的子序列,因此同样可以用DP来解决。定义数组的存储含义对于后面推导转移方程显得尤为重要,糟糕的数组定义会导致异常繁杂的转移方程。考虑到子串的连续性,将二维数组c[i][j]用来记录具有这样特点的子串——结尾同时也为为串x1x2&#8943;xix1x2&#8943;xi与y1y2&#8943;yjy1y2&#8943;yj的结尾——的长度。

得到转移方程:

最长公共子串的长度为 max(c[i,j]), i∈{1,&#8943;,m},j∈{1,&#8943;,n}max(c[i,j]), i∈{1,&#8943;,m},j∈{1,&#8943;,n}

代码实现

public static int lcs(String str1, String str2) {
 int len1 = str1.length();
 int len2 = str2.length();
 int result = 0; //记录最长公共子串长度
 int c[][] = new int[len1+1][len2+1];
 for (int i = 0; i <= len1; i++) {
 for( int j = 0; j <= len2; j++) {
  if(i == 0 || j == 0) {
  c[i][j] = 0;
  } else if (str1.charAt(i-1) == str2.charAt(j-1)) {
  c[i][j] = c[i-1][j-1] + 1;
  result = max(c[i][j], result);
  } else {
  c[i][j] = 0;
  }
 }
 }
 return result;
}

总结

以上就是这篇文章的全部内容改了,希望本文的内容对大家的学习或者工作能带来一定的帮助,如果有疑问大家可以留言交流。


推荐阅读
  • 优化ListView性能
    本文深入探讨了如何通过多种技术手段优化ListView的性能,包括视图复用、ViewHolder模式、分批加载数据、图片优化及内存管理等。这些方法能够显著提升应用的响应速度和用户体验。 ... [详细]
  • Søren Kierkegaard famously stated that life can only be understood in retrospect but must be lived moving forward. This perspective delves into the intricate relationship between our lived experiences and our reflections on them. ... [详细]
  • 本文详细探讨了Java中的24种设计模式及其应用,并介绍了七大面向对象设计原则。通过创建型、结构型和行为型模式的分类,帮助开发者更好地理解和应用这些模式,提升代码质量和可维护性。 ... [详细]
  • 本文介绍了Java并发库中的阻塞队列(BlockingQueue)及其典型应用场景。通过具体实例,展示了如何利用LinkedBlockingQueue实现线程间高效、安全的数据传递,并结合线程池和原子类优化性能。 ... [详细]
  • 题目描述:给定n个半开区间[a, b),要求使用两个互不重叠的记录器,求最多可以记录多少个区间。解决方案采用贪心算法,通过排序和遍历实现最优解。 ... [详细]
  • 深入理解C++中的KMP算法:高效字符串匹配的利器
    本文详细介绍C++中实现KMP算法的方法,探讨其在字符串匹配问题上的优势。通过对比暴力匹配(BF)算法,展示KMP算法如何利用前缀表优化匹配过程,显著提升效率。 ... [详细]
  • 探讨一个显示数字的故障计算器,它支持两种操作:将当前数字乘以2或减去1。本文将详细介绍如何用最少的操作次数将初始值X转换为目标值Y。 ... [详细]
  • 本文详细介绍了Java编程语言中的核心概念和常见面试问题,包括集合类、数据结构、线程处理、Java虚拟机(JVM)、HTTP协议以及Git操作等方面的内容。通过深入分析每个主题,帮助读者更好地理解Java的关键特性和最佳实践。 ... [详细]
  • 本文探讨如何设计一个安全的加密和验证算法,确保生成的密码具有高随机性和低重复率,并提供相应的验证机制。 ... [详细]
  • 深入解析:手把手教你构建决策树算法
    本文详细介绍了机器学习中广泛应用的决策树算法,通过天气数据集的实例演示了ID3和CART算法的手动推导过程。文章长度约2000字,建议阅读时间5分钟。 ... [详细]
  • 在金融和会计领域,准确无误地填写票据和结算凭证至关重要。这些文件不仅是支付结算和现金收付的重要依据,还直接关系到交易的安全性和准确性。本文介绍了一种使用C语言实现小写金额转换为大写金额的方法,确保数据的标准化和规范化。 ... [详细]
  • 在给定的数组中,除了一个数字外,其他所有数字都是相同的。任务是找到这个唯一的不同数字。例如,findUniq([1, 1, 1, 2, 1, 1]) 返回 2,findUniq([0, 0, 0.55, 0, 0]) 返回 0.55。 ... [详细]
  • 本文探讨了卷积神经网络(CNN)中感受野的概念及其与锚框(anchor box)的关系。感受野定义了特征图上每个像素点对应的输入图像区域大小,而锚框则是在每个像素中心生成的多个不同尺寸和宽高比的边界框。两者在目标检测任务中起到关键作用。 ... [详细]
  • 网络攻防实战:从HTTP到HTTPS的演变
    本文通过一系列日记记录了从发现漏洞到逐步加强安全措施的过程,探讨了如何应对网络攻击并最终实现全面的安全防护。 ... [详细]
  • 本文深入探讨了Linux系统中网卡绑定(bonding)的七种工作模式。网卡绑定技术通过将多个物理网卡组合成一个逻辑网卡,实现网络冗余、带宽聚合和负载均衡,在生产环境中广泛应用。文章详细介绍了每种模式的特点、适用场景及配置方法。 ... [详细]
author-avatar
何zzz小宝
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有