LCS（最长公共子串）系列问题

绝地灬酷狼 2022-05-08 03:58 176阅读 0赞

## 问题一 ##

探索递归模式下，电脑最长计算的长度情况。（我也很神秘，为什么老师要出这种问题。。。）

就是不断修改下面的`n`，来看看数值就知道了~

#include <iostream>
    using namespace std;
    #include <string>
    
    string multiply(string s, int time) { 
    	string t;
    	for (int i = 0; i < time; ++i) t = t + s;
    	return t;
    }
    
    string x, y;
    
    int lcs(int i, int j) { 
    	if (i == 0 || j == 0) return 0;
    	if (x[i] == y[j]) return lcs(i - 1, j - 1) + 1;
    	int temp1 = lcs(i - 1, j);
    	int temp2 = lcs(i, j - 1);
    	if (temp1 > temp2) return temp1;
    	return temp2;
    }
    
    int main() { 
    	x = "123";
    	y = "12";
    	int n = 16;
    
    	x = multiply(x, n);
    	y = multiply(y, n);
    
    	cout << lcs(x.length(), y.length()) << endl;
    	system("pause");
    }

## 递推实现，并输出路径 ##

#include <iostream>
    using namespace std;
    #include <string>
    
    int lcs(string A, string B, string &C, int n, int m) { 
    	int i, j, k;
    	int **L = new int*[n + 1];
    	for (i = 0; i <= n; ++i) L[i] = new int[m + 1];
    	int **S = new int*[n + 1];
    	for (i = 0; i <= n; ++i) S[i] = new int[m + 1];
    
    	for (i = 0; i <= n; ++i) L[i][0] = 0;
    	for (j = 0; j <= m; ++j) L[0][j] = 0;
    	for (i = 1; i <= n; ++i) { 
    		for (j = 1; j <= m; ++j) { 
    			if (A[i-1] == B[j-1]) { 
    				L[i][j] = L[i - 1][j - 1] + 1;
    				S[i][j] = 1;
    			}
    			else if (L[i - 1][j] >= L[i][j - 1]) { 
    				L[i][j] = L[i - 1][j];
    				S[i][j] = 2;
    			}
    			else { 
    				L[i][j] = L[i][j - 1];
    				S[i][j] = 3;
    			}
    		}
    	}
    	k = L[n][m];
    	C = "";
    	for (i = 0; i < k; ++i) C.append("0");
    	i = n, j = m;
    	while (i != 0 && j != 0) { 
    		switch (S[i][j])
    		{ 
    		case 1:
    			C[k-1] = A[i-1]; i--; j--; k--; break;
    		case 2:
    			i--; break;
    		case 3:
    			j--; break;
    		}
    	}
    	int ans = L[n][m];
    	for (i = 0; i <= n; ++i) delete L[i];
    	delete[] L;
    	for (i = 0; i <= n; ++i) delete S[i];
    	delete[] S;
    	return ans;
    }
    
    int main() { 
    	string X = "bcdbadce", Y = "cabdcbc", Z="";
    	cout << lcs(X, Y, Z, X.length(), Y.length()) << endl;
    	cout << Z << endl;
    	system("pause");
    }

**输出：**

4
    bcbc

思路其实很简单，按照之前做的划分方式就好了。

**难点：** 在于为什么写为`A[i-1] = = B[i-1]` 还有就是后面有一个`C[k-1] = A[i-1];`

**解释：** 因为全局的`i , j`都是表示的前面还有多个剩余串数量，也就是是**index +1** 所以这里定位回去到index的时候，就需要减一了。

## 问题三 ##

递归式的，但是要求输出序列。

#include <iostream>
    using namespace std;
    #include <string>
    
    typedef pair<string, int> DATA;
    
    string X = "bcdbadce", Y = "cabdcbc";
    
    DATA lcs(int i, int j) { 
    	if (i == 0 || j == 0) return { "", 0};
    	
    	if (X[i-1] == Y[j-1]) {  
    		DATA temp = lcs(i - 1, j - 1);
    		temp.first.push_back(X[i-1]);
    		temp.second++;
    		return temp;
    	}
    	
    	DATA temp1 = lcs(i - 1, j);
    	DATA temp2 = lcs(i, j - 1);
    	if (temp1.second >= temp2.second) return temp1;
    	return temp2;
    }
    
    int main() { 
    	DATA temp = lcs(X.length(), Y.length());
    	cout << temp.first << "\n" << temp.second << endl;
    	system("pause");
    }

输出为：

bcbc
    4