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

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

source code

https://github.com/haotang923/interview/tree/master/LCS

 

两个字符串求最长公共子串(Longest Common Substring)最长公共子序列(Longest Common Subsequence)的区别:子串要求在原字符串中是连续的,而子序列则只需保持相对顺序一致,并不要求连续。例如X = {a, Q, 1, 1}; Y = {a, 1, 1}。那么,{a, 1, 1}是X和Y的最长公共子序列,但不是它们的最长公共字串。

给定母串X=<x1,x2,,xm>,Y=<y1,y2,⋯,yn>。

用二维数组c[ij]记录结尾为xi与yj的子串的LCS长度,则最长公共子串状态转移方程如下

最长公共子串长度为max { c[i, j] }。

用二维数组c[i, j]记录x1...xi与y1...yj的LCS长度,则最长公共子序列状态转移方程如下

最长公共子序列长度为c[m, n]。

注意代码中string下标从0开始,所以循环体内判断使用(str1[i - 1] == str2[j - 1])。

  • 【动态规划】最长公共子序列与最长公共子串 - Treant - 博客园
    • http://www.cnblogs.com/en-heng/p/3963803.html
  • 【动态规划】Dynamic Programming - 神奕的专栏 - CSDN博客
    • http://blog.csdn.net/lisonglisonglisong/article/details/41548557
  • 【动态规划】输出所有的最长公共子序列 - 神奕的专栏 - CSDN博客
    • http://blog.csdn.net/lisonglisonglisong/article/details/41596309
  • 动态规划:求最长公共子串/最长公共子序列 - Sunshine的专栏 - CSDN博客
    • http://blog.csdn.net/u013074465/article/details/45392687
1 // 2 //  main.cpp 3 //  LeetCode 4 // 5 //  Created by Hao on 2017/3/16. 6 //  Copyright © 2017年 Hao. All rights reserved. 7 // 8  9 #include 
10 #include
11 using namespace std;12 13 class Solution {14 public:15 int longestCommonSubstring(const string &str1, const string &str2) {16 vector< vector
> f(str1.size() + 1, vector
(str2.size() + 1) ); // 二维数组17 int result = 0;18 19 for (auto i = 0; i < str1.size() + 1; i ++) {20 for (auto j = 0; j < str2.size() + 1; j ++) {21 if (i == 0 || j == 0) // i == 0 or j == 022 f[i][j] = 0;23 else if (str1.at(i - 1) == str2.at(j - 1)) { // i, j > 0 and str1[i - 1] == str2[j - 1]24 f[i][j] = f[i - 1][j - 1] + 1;25 if (f[i][j] > result) result = f[i][j]; // 最长公共子串26 } else // i, j > 0 and str1[i - 1] != str2[j - 1], 区别于求最长公共子序列27 f[i][j] = 0;28 }29 }30 31 return result;32 }33 34 int longestCommonSubsequence(const string &str1, const string &str2) {35 vector< vector
> f(str1.size() + 1, vector
(str2.size() + 1) ); // 二维数组36 int result = 0;37 38 for (auto i = 0; i < str1.size() + 1; i ++) {39 for (auto j = 0; j < str2.size() + 1; j ++) {40 if (i == 0 || j == 0) // i == 0 or j == 041 f[i][j] = 0;42 else if (str1.at(i - 1) == str2.at(j - 1)) { // i, j > 0 and str1[i - 1] == str2[j - 1]43 f[i][j] = f[i - 1][j - 1] + 1;44 } else // i, j > 0 and str1[i - 1] != str2[j - 1], 区别于求最长公共子串45 f[i][j] = max(f[i][j - 1], f[i - 1][j]);46 }47 }48 49 // 矩阵最后一个元素50 result = f[str1.size()][str2.size()];51 52 return result;53 }54 };55 56 int main ()57 {58 Solution testSolution;59 60 vector
vecTest1{ { "ABCBDAB"}, { ""}, { "ABC"}, { "ABC"} };61 vector
vecTest2{ { "BDCABA"}, { ""}, { "DEF"}, { "ABC"} };62 63 for (auto i = 0; i < vecTest1.size(); i ++)64 cout << testSolution.longestCommonSubstring(vecTest1[i], vecTest2[i]) << endl;65 66 for (auto i = 0; i < vecTest1.size(); i ++)67 cout << testSolution.longestCommonSubsequence(vecTest1[i], vecTest2[i]) << endl;68 69 return 0;70 }
View Code

 

转载于:https://www.cnblogs.com/pegasus923/p/7573973.html

你可能感兴趣的文章
AccountManagerCallback<V>
查看>>
为什么入门首选C言语
查看>>
我的友情链接
查看>>
ubuntu 命令详解及使用技巧
查看>>
第1章 方法的概述及基本使用
查看>>
Linux学习—LVM快照功能
查看>>
关于CSS中 星号*的使用介绍
查看>>
好程序员Web前端教程分享Vue学习心得
查看>>
深入简出 好程序员教你HTML5开发基本常识
查看>>
HTTP和HTTPS详解。
查看>>
记录RBA(redo byte address)
查看>>
Oracle教程之管理UNDO(二)--监视UNDO表空间
查看>>
RAC在线替换OCR、DATA、FRA等ASM磁盘
查看>>
[Office]使用 Microsoft Office Live Workspace
查看>>
编译安装与RPM安装的区别
查看>>
我的友情链接
查看>>
linux下ftp的安全巧用之pureftp!
查看>>
初始化AppWidget框架结构
查看>>
[PHP] 文件系统交互
查看>>
我的友情链接
查看>>