最長(zhǎng)公共子序列：

如果要回溯出整個(gè)字符串的答案的話，可以直接看dp[i][len2-1]列，或者dp[len1-1][i]這一行，變化的時(shí)候，則代表要選這個(gè)字符，然后連起來(lái)就可以了。（即構(gòu)造字符串的過(guò)程是On的）?

class Solution { public:/*** longest common substring* @param str1 string字符串 the string* @param str2 string字符串 the string* @return string字符串*/int dp[5005][5005];string LCS(string str1, string str2) {// write code hereint len1 = str1.size();int len2 = str2.size();for(int i = 0; i<len1; i++) dp[i][0] = (str1[i] == str2[0])?1:dp[i-1][0];for(int i = 0; i<len2; i++) dp[0][i] = (str1[0] == str2[i])?1:dp[0][i-1];for(int i = 1; i<len1; i++) {for(int j = 1; j<len2; j++) {if(str1[i] == str2[j]) dp[i][j] = dp[i-1][j-1] + 1;else dp[i][j] = max(dp[i-1][j-1], max(dp[i-1][j], dp[i][j-1]));}}for(int i = 0; i<len1; i++) {for(int j = 0; j<len2; j++) {cout << dp[i][j] << " ";}cout << endl;}cout << dp[len1-1][len2-1] <<endl;return str1;} };

最長(zhǎng)公共子串：

class Solution { public:/*** longest common substring* @param str1 string字符串 the string* @param str2 string字符串 the string* @return string字符串*/int dp[5005][5005];string LCS(string str1, string str2) {// write code hereint len1 = str1.size();int len2 = str2.size();for(int i = 0; i<len1; i++) dp[i][0] = (str1[i] == str2[0])?1:0;for(int i = 0; i<len2; i++) dp[0][i] = (str1[0] == str2[i])?1:0;for(int i = 1; i<len1; i++) {for(int j = 1; j<len2; j++) {if(str1[i] == str2[j]) dp[i][j] = dp[i-1][j-1] + 1;else dp[i][j] = 0;}}int mx = 0;string ans;for(int i = 0; i<len1; i++) {for(int j = 0; j<len2; j++) {if(dp[i][j] > mx) {mx = dp[i][j];ans = str1.substr(i-mx+1, mx);}}}return ans;} };

總結(jié)

以上是生活随笔為你收集整理的【LCS系列】最长公共子序列和最长公共子串的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。