求最长子序列和最长公共子串

xiaoxiao2025-07-18  12

又有一段时间没刷题,今天温故下,最长公共子序列和最长公共子串概念不一样,子序列可以不连续,子串必须连续,这两题均可以用动态规划解决!,下面程序在VS上跑过无问题!

#include<iostream> #include<string> #include<algorithm> #include<cmath> using namespace std; //动态规划求最长子序列 int LongestCommonSeq(string s1, string s2) { int m = s1.size()+1; int n = s2.size()+1; cout << m << n << endl; int** dp = (int**)malloc(sizeof(int *)*m); for (int i = 0; i <= m; i++) { dp[i] = (int *)malloc(sizeof(int)*n); } for (int i = 0; i <= m; i++) { for (int j = 0; j <= n; j++) { if (i == 0 || j == 0) { dp[i][j] = 0; } else if (s1[i-1] == s2[j-1]) { dp[i][j] = dp[i - 1][j - 1] + 1; } else { dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); } } } return dp[m-1][n-1]; } //动态规划求解最长连续子串 string LongConsecStr(string s1, string s2) { int m = s1.size(); int n = s2.size(); int index = 0; int **dp = (int**)malloc(sizeof(int *)*m); for (int i = 0; i <= m; i++) { dp[i] = (int *)malloc(sizeof(int)*n); } int max = -1; for (int i = 0; i <= m; i++) { for (int j = 0; j <= n; j++) { if (i == 0 || j == 0) { dp[i][j] = 0; } else if(s1[i - 1] == s2[j - 1]) { dp[i][j] = dp[i - 1][j - 1] + 1; } else { dp[i][j] = 0; } if (max < dp[i][j]) { max = dp[i][j]; index = i; } } } return s1.substr(index - max, index); } int main() { string s1 = "ABHDF"; string s2 = "BCDFG"; int res1 = LongestCommonSeq(s1, s2); string res2 = LongConsecStr(s1, s2); cout<< res1<<" "<<res2 << endl; return 0; }
转载请注明原文地址: https://www.6miu.com/read-5033263.html

最新回复(0)