最长公共子串（LCS）

本文主要是介绍最长公共子串（LCS），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

(1) 找出两个字符串的最长公共子串

题目：输入两个字符串，找出两个字符串中最长的公共子串。

找两个字符串的最长公共子串，这个子串要求在原字符串中是连续的。

#include<iostream>
#include<string>
using namespace std;
int main()
{string s1 = "GCCCTAGCCAGDE";string s2 = "GCGCCAGTGDE ";int len1 = s1.size();int len2 = s2.size();int** c = new int* [len1];for (int i = 0; i < len1; i++){c[i] = new int[len2];memset(c[i], 0, sizeof(int)*len2);}int start = -1;int end = -1;int maxLen = 0;for (int i = 0; i < len1; i++){for (int j = 0; j < len2; j++){if (s1[i] == s2[j]){int indexI = i == 0 ? 0 : (i - 1);int indexJ = j == 0 ? 0 : (j - 1);c[i][j] = c[indexI][indexJ] + 1;if (c[i][j] > maxLen){maxLen = c[i][j];end = i;start = i - c[i][j] + 1;}}else{c[i][j] = 0;}}}if (maxLen != 0){string res = s1.substr(start, maxLen);cout << res << endl;}for (int i = 0; i < len1; i++){delete[] c[i];}return 0;
}

(2) 找出两个字符串的最长公共子序列

题目：输入两个字符串，求两个字符串的最长公共子序列。

首先，最长公共子序列与最长公共子串不同，子序列不要求其在原字符串是连续的。例如字符串$X=\{A,B,C,B,D,A,B\}$，$Y = \{B,D,C,A,B,A\}$，则X与Y的最长公共子序列为$Z=\{B,C,B,A\}$;

#include<iostream>
#include<string>
using namespace std;
string getLongestSequence(string s1, string s2)
{int len1 = s1.size();int len2 = s2.size();int** c = new int* [len1];for (int i = 0; i < len1; i++){c[i] = new int[len2];memset(c[i], 0, sizeof(int)*len2);}int start = -1;int end = -1;int maxLen = 0;for (int i = 0; i < len1; i++){for (int j = 0; j < len2; j++){if (s1[i] == s2[j]){int preMax = (i == 0 || j == 0) ? 0 : c[i - 1][j - 1];c[i][j] = preMax + 1;}else{int preMax1 = (i == 0) ? 0 : c[i - 1][j];int preMax2 = (j == 0) ? 0 : c[i][j - 1];c[i][j] = max(preMax1, preMax2);}if (c[i][j] > maxLen){maxLen = c[i][j];}}}string res(maxLen, '-');for (int i = len1 - 1, j = len2 - 1, index = maxLen; i >= 0 && j >= 0;){int preC1 = i == 0 ? -1 : c[i - 1][j];//说明s1[i]字符不在最大子序列里if (c[i][j] == preC1){i--;continue;}//说明s1[i]字符在最大子序列里else{//更新结果res[--index] = s1[i];//说明s2[j]字符不在最大子序列里int preC2 = j == 0 ? -1 : c[i][j - 1];while (c[i][j] == preC2){j--;}i--;j--;}}return res;for (int i = 0; i < len1; i++){delete[] c[i];}
}
int main()
{string s1 = "ABCBDAB";string s2 = "BDCABA";string res1 = getLongestSequence(s1, s2);string res2 = getLongestSequence(s2, s1);if (strcmp(res1.c_str(), res2.c_str())){cout << res1 << endl;cout << res2 << endl;}else{cout << res1 << endl;}return 0;
}

这篇关于最长公共子串（LCS）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---