算法之搜索--最长公共子序列LCS

最长公共子序列（longest common sequence）:可以不连续

最长公共子串（longest common substring）：连续

demo

for (int i = 1;i<=lena;i++){
for (int j = 1;j<=lenb;j++){
if(a[i-1]==b[j-1]){
dp[i][j]=dp[i-1][j-1]+1;
}else{
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}
}
}

Coincidence

题目描述

Time Limit: 1000 ms
Memory Limit: 256 mb
Find a longest common subsequence of two strings.

输入描述:

First and second line of each input case contain two strings of lowercase character a…z. There are no spaces before, inside or after the strings. Lengths of strings do not exceed 100.

输出描述:

For each case, output k – the length of a longest common subsequence in one line.

代码

#include <bits/stdc++.h>
using namespace std;

int dp[105][105];

void LCS(string a,string b){
int lena = a.length();
int lenb = b.length();
for(int i = 1;i<=lena;i++){
for(int j = 1;j<=lenb;j++){
if(a[i-1]==b[j-1]){//注意不是i,j
dp[i][j]=dp[i-1][j-1]+1;
}else{
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}
}
}
}


int main(){
string a,b;
while(cin>>a>>b){
int lena = a.length();
int lenb = b.length();
LCS(a,b);
cout<<dp[lena][lenb]<<endl;
}
return 0;
}

最长公共子序列

题目描述

Time Limit: 1000 ms
Memory Limit: 256 mb
给出两个字符串序列，求最长公共子序列（LCS） 。（改编版，原题规定两字符串长度相等，且无重复元素。）

输入描述:

多组数据输入。
在一行分别输入两个字符串。(字符串长度<=1000)

输出描述:

输出两个字符串的最长公共子序列的长度。

代码

#include <bits/stdc++.h>
using namespace std;

int dp[1005][1005];

void LCS(string a,string b){
int lena = a.length();
int lenb = b.length();
for(int i = 1;i<=lena;i++){
for(int j = 1;j<=lenb;j++){
if(a[i-1]==b[j-1]){//注意不是i,j
dp[i][j]=dp[i-1][j-1]+1;
}else{
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}
}
}
}

int main(){
string a,b;
while(cin>>a>>b){
int lena = a.length();
int lenb = b.length();
LCS(a,b);
cout<<dp[lena][lenb]<<endl;
}
return 0;
}

最长连续公共子序列

原文地址：https://blog.csdn.net/sinat_40546227/article/details/114795742

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！