【LeetCode】最长公共子序列
2024-10-08 16:59:33
【问题】给定两个字符串A和B,长度分别为m和n,要求找出它们最长的公共子串,并返回其长度。例如:
A = "HelloWorld"
B = "loop"
则A与B的最长公共子串为 "lo",返回的长度为2。
【思路】最长公共子串的问题不同于最长公共子序列,由于子串的连续的,而子序列不一定连续。在上一个子序列中dp[i][j]是非减的,因此最后返回最大公共子序列时,返回的是dp[n][m]。而在最大子串问题中,dp[i][j]可能小于dp[i-1][j-1],因此需要一个res来保存更新最大值。
通俗考虑,在两个子串中寻找,假设a[i]==b[j]了,那么从i和j向后走,res会一直更新变大,一旦遇到不相等时,则dp[i][j]清零,寻找下一个重复的子串。因此其递推式为:
其中dp[i][0] = 0, dp[0][j] = 0;
class LongestSubstring {
public:
int findLongest(string A, int n, string B, int m) {
if(n == || m == )
return ;
int rs = ;
int dp[n + ][m + ];
for(int i = ; i <= n; i++)//初始状态
dp[i][] = ;
for(int i = ; i <= m; i++)
dp[][i] = ;
for(int i = ; i <= n; i++)
for(int j = ; j<= m; j++)
{
if(A[i - ] == B[j - ])
{
dp[i][j] = dp[i -][j - ] + ;
rs = max(rs,dp[i][j]);//每次更新记录最大值
} else//不相等的情况
dp[i][j] = ;
}
return rs;//返回的结果为rs
}
};
最新文章
- 同步与异步 &; 阻塞与非阻塞
- Mac下安装GIT的坑
- 在windows7 上安装 Sublime Text 3 及其插件
- 【C#】委托
- zw版【转发&#183;台湾nvp系列例程】halcon与delphi系列例程
- .NET开源工作流RoadFlow-系统布署中常见错误及处理方法
- #define XXX do{...}while(0)
- 【原】数据库SQL语句入门
- python_getpass 模块的使用
- 让织梦内容页arclist标签的当前文章标题加亮显示
- Shiro授权管理
- nginx: [emerg] getpwnam(";nginx";) failed
- 前端web服务器数据同步方案
- 用mysql workbench导出mysql数据库关系图
- 几种流行的AJAX框架对比:Jquery,Mootools,Dojo,ExtJs,Dwr
- 手写自己的ThreadLocal(线程局部变量)
- 前端_html
- SocketServer模块 《Python核心编程(第3版)》——2.5
- sql语句-3-聚合数据查询
- Elasticsearch NEST使用指南:映射和分析