兩字元串最長公共子序列--動态規劃連續和非連續

史上最全最豐富的“最長公共子序列”、“最長公共子串”問題的解法與思路

https://blog.csdn.net/wangdd_199326/article/details/76464333

非連續的最長公共子序列

求兩個字元串的最長公共子序列。借用算法導論上的表示方法，給定一個字元串X=<x_1,x_2,...,x_m>（下劃線後面的數字表示下标），另一個字元串Y=<y_1,y_2,...,y_n>，求X和Y的最長公共子序列。同時我們用X_i表示X中前i個字元構成的字元串X_i = <x_1,...,x_i>，用Y_j表示Y紅前j個字元構成的字元串Y_j = <y_1,y_2,...,y_j>。

現在就想怎麼把問題變為為小問題呢？怎麼解決這個問題呢？

關鍵要找到問題的突破口，先不要管最終解決，先想一想怎麼吧問題花姐的規模小一些。我先分别拿兩個字元串的最後一個字元“開刀”，先拿他們比較

1）我們可以首先比較x_m和y_n如果這兩個字元相同，那麼x_m = y_n一定是最長公共子序列中的一個字元。那麼我們的問題就是求X_(m-1) = <x_1,...,x_(m-1)>和Y_(n-1) = <y_1,...,y_(n-1)>的最長公共子序列了。如果能求出X_(m-1)和Y_(n-1)的最長公共子序列，這個子序列在加上字元x_m = y_n就是我們所求問題的最長公共子序列了。

2）如果x_m ！= y_n，我們要求X和Y的最長公共最序列，就轉為求兩個子問題，一個是求X_m和Y_(n-1)的最長公共子序列，另一個是求X_(m-1)和Y_n的最長公共子序列。取兩者中最長的那個就是問題的解。

至此，大問題就化為小問題的，具體我們可以寫遞推公式。

假如用c[i,j]表示X_i和Y_j序列的最大公共子序列的長度的話

c[i,j] = 0 如果i == 0或者j == 0

c[i,j] = c[i - 1][j - 1] 如果x_j == y_j

c[i,j] = max(c[i-1,j], c[i, j-1])   如果x_i ！= y_j
           

有了遞推公式，定義對應遞推公式的數組，就可以求得最終的答案。

#include<iostream>
#include<string>
#include<vector>
using namespace std;
 
int max(const int& a, const int& b) {
	return (a > b ? a : b);
}
 
//模闆函數用來輸出二維數組
template<class Type>
void print_vector(const vector<vector<Type> >& vec) {
	for(size_t i = 0; i != vec.size(); i++) {
		for(size_t j = 0; j != vec[i].size(); j++) {
			cout << vec[i][j] << " ";
		}
		cout << endl;
	}
}
//getLCS函數用來求兩個字元串的最大公共子序列，并傳回其長度
int getLCS(const string& str1, const string& str2){
	if(str1.empty() || str2.empty()) {
		return 0;
	}
	size_t len1 = str1.size();
	size_t len2 = str2.size();
	
	//lcs用來儲存兩字元串str1[0,...,row]和str1[0,...,col]的最長公共序列的長度
	vector<vector<int> > lcs(len1 + 1, vector<int> (len2 + 1, 0));
 
	//index用來儲存如何找到最長公共子序列
	vector<vector<char> > index(len1 + 1, vector<char> (len2 + 1, '-'));
	for(size_t row = 0; row != len1 + 1; row++) {
		for(size_t col = 0; col != len2 + 1; col++) {
			if(row == 0 || col == 0) {
				lcs[row][col] = 0;
				continue;
			}
			if(str1[row - 1] == str2[col - 1]) {
				lcs[row][col] = lcs[row - 1][col - 1] + 1;
				index[row][col] = '=';
			}
			if(str1[row - 1] != str2[col - 1]) {
				//lcs[row][col] = max(cls[row - 1][col], cls[row][col - 1]);
				if(lcs[row - 1][col] > lcs[row][col - 1]) {
					lcs[row][col] = lcs[row - 1][col];
					index[row][col] = 'u';
				}
				else {
					lcs[row][col] = lcs[row][col - 1];
					index[row][col] = 'l';
				}
			}
		}
	}
	cout << "lcs vector is " << endl;
	print_vector(lcs);
	cout << "index vector is " << endl;
	print_vector(index);
	return lcs[len1][len2];
}
 
int main(void)
{
	string str1, str2;
	cin >> str1 >> str2;
	int len = 0;
	len = getLCS(str1, str2);
	cout << "最長公共子序列的長度是：" << len << endl;
	return 0;
}
           

 兩個字元串最長連續公共序列

如下兩個字元串,公共連續字元串為abcdf，求出這個abcdf，

"aaffffsfabcdfasf", "aaaadfsabcdfsdb"

假設字元串長度分别為m,n，這個題有個m*n*min(m,n)複雜度的方法，這個方法比較慢，暫時不考慮。

另一個種方法是動态規劃：

設定二維數組dp[][], dp[i][j]==0表示第一個字元串的第i個字元與第二個字元串的第j個字元不相等，dp[i][j]!=0表示第一個字元串的第i個字元與第二個字元串的第j個字元串相等，并且，如果dp[i][j]==k，不僅目前字元相等，前面k-1個也相等，也就是dp的公式為dp[i][j] = dp[i-1][j-1]+1。最終二維矩陣的結果如下所示（随機寫的）：

00010010

01000000

00201000

01030010

11014101

代碼如下：

//求兩個字元串的最大公共字串
	public String longestSerialSubstring(String s1,String s2){
		String res = "";
		
		int m = s1.length(),n = s2.length();
		int[][] dp = new int[m][n];
		
		int max = 0;
		int index = 0;
		
		for(int i=0;i<m;i++){
			for(int j=0;j<n;j++){
				char c1 = s1.charAt(i);
				char c2 = s2.charAt(j);
				
				if(c1==c2){
					if(i==0 || j==0){
						dp[i][j] = 1;
					}else{
						dp[i][j] = dp[i-1][j-1] + 1;
					}
					if(dp[i][j]>max){
						max = dp[i][j];
						index = i;
					}
				}
			}
		}
		res = s1.substring(index-max+1,index+1);
		return res;
	}