算法之搜索--最长公共子序列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;
}

最长连续公共子序列