最长公共子序列(LCS)问题
2024-09-04 01:09:22
最长公共子串(Longest Common Substirng)和最长公共子序列(Longest Common Subsequence,LCS)的区别为:子串是串的一个连续的部分,子序列则是从不改变序列的顺序,而从序列中去掉任意的元素而获得新的序列;也就是说,子串中字符的位置必须是连续的,子序列则可以不必连续。
1、序列str1和序列str2
·长度分别为m和n;
·创建1个二维数组L[m.n];
·初始化L数组内容为0
·m和n分别从0开始,m++,n++循环:
- 如果str1[m] == str2[n],则L[m,n] = L[m - 1, n -1] + 1;
- 如果str1[m] != str2[n],则L[m,n] = max{L[m,n - 1],L[m - 1, n]}
·最后从L[m,n]中的数字一定是最大的,且这个数字就是最长公共子序列的长度
·从数组L中找出一个最长的公共子序列
2、从数组L中查找一个最长的公共子序列
i和j分别从m,n开始,递减循环直到i = 0,j = 0。其中,m和n分别为两个串的长度。
·如果str1[i] == str2[j],则将str[i]字符插入到子序列内,i--,j--;
·如果str1[i] != str[j],则比较L[i,j-1]与L[i-1,j],L[i,j-1]大,则j--,否则i--;(如果相等,则任选一个)
我们可以得到其中公共子串:B C B A 和 B D A B。
#include <iostream>
#define N 1000
using namespace std; //c[i][j]存储str1[1...i]与str2[1...j]的最长公共子序列的长度
int c[N][N];
//flag[i][j]标记是那种子问题
//flag[i][j]==0为str1[i]==str2[j]
//flag[i][j]==1为c[i-1][j]>=s[i][j-1]
//flag[i][j]==-1为c[i-1][j]<s[i][j-1]
int flag[N][N]; int getLCSlength(string str1, string str2)
{
int len1 = str1.size();
int len2 = str2.size();
for (int i = ; i <= len1; i++)
{
for (int j = ; j <= len2; j++)
{
if (i == || j == )
c[i][j] = ;
else if (str1[i - ] == str2[j - ])
{
c[i][j] = c[i - ][j - ] + ;
flag[i][j] = ;
}
else if (c[i - ][j] >= c[i][j - ]){
c[i][j] = c[i - ][j];
flag[i][j] = ;
}
else{
c[i][j] = c[i][j - ];
flag[i][j] = -;
}
}
}
return c[len1][len2];
} void getLCS(string s1, string s2,int len,char *lcs)
{
int i = s1.size();
int j = s2.size();
while(i&&j)
{
if(flag[i][j]==)
{
lcs[--len] = s1[i-];
i--;
j--;
}
else if(flag[i][j]==) //往上
i--;
else if(flag[i][j]==-)//往左
j--;
} } int main()
{
string str1,str2,lcs;
char lcs[N];
cout<<"请输入字符串1:"<<endl;
cin>>str1;
cout<<"请输入字符串2:"<<endl;
cin>>str2; int lcsLen = getLCSlength(str1,str2);
cout<<"最长公共子序列长度:"<<lcsLen<<endl; getLCS(str1,str2,lcsLen,lcs);
cout<<"最长公共子序列为:";
for(int i=;i<lcsLen;i++)
cout<<lcs[i];
return ;
}
最新文章
- 《利用python进行数据分析》读书笔记--第八章 绘图和可视化
- [LintCode] Add Binary 二进制数相加
- ie9始终提示文档预览需要最新版本的Flash Player支持的解决方法:
- *[hackerrank]Algorithmic Crush
- javascript 学习笔记之模块化编程
- Ruby on Rails Session 2: How to install Aptana Studio 3 on Ubuntu 12.04 LTS
- 简单的Session登录
- Codeforces Round #270--B. Design Tutorial: Learn from Life
- 企业架构研究总结(30)——TOGAF架构内容框架之内容元模型(上)
- validform 怎么验证小数。
- 【webpack】中clean-weabpack-plugin使用方法
- 压缩(zip)
- node csv
- 利用sql server直接创建日历
- SQL Server表描述 及 字段描述的增、删、改、查询
- iOS:文字相关(19-01-08更)
- CF839 B 贪心
- T-SQL 之 控制流语句
- Python模块学习 - openpyxl
- Venom的简单使用
热门文章
- Codeforces Round #378 (Div. 2) D. Kostya the Sculptor 分组 + 贪心
- SpringBoot整合Redis使用Restful风格实现CRUD功能
- Java中的Validated验证
- 结合源码看nginx-1.4.0之nginx内存管理详解
- Java基础语法(Eclipse)
- ecshop分类页把分类描述改成FCKeditor编辑器
- Garmin APP开发之布局
- SQL SEVER数据库重建索引的方法
- WAMP安装提示缺少 msvcr100.dll文件解决方法
- 在Linux系统里安装Virtual Box的详细步骤