最長公共子序列

05-01

#include <iostream>#include <math.h>#include <string>using namespace std;//普通遞歸求解int LCS_Recur (string str1, string str2){ int len1 = str1.length(); int len2 = str2.length(); if(len1 == 0 || len2 == 0) return 0; else if(str1[len1-1] == str2[len2-1]){ string str_1 = str1.substr(0, len1-1); string str_2 = str2.substr(0, len2-1); return LCS_Recur(str_1, str_2) + 1; //減而治之 } else{ string str_1 = str1.substr(0, len1-1); string str_2 = str2.substr(0, len2-1); return max(LCS_Recur(str_1, str2), LCS_Recur(str1, str_2));//分而治之 }}//動態規劃求解int LCS_DP(string str1, string str2){ int len1 = str1.length(); int len2 = str2.length(); int **chart = new int *[len2+1]; for(int i = 0; i <= len2; i++){ chart[i] = new int[len1+1]; memset(chart[i], 0, sizeof(int)*(len1+1)); } for(int i = 1; i <= len2; i++){ for(int j = 1; j <= len1; j++){ if(str1[j-1] == str2[i-1]) chart[i][j] = chart[i-1][j-1] + 1; //減而治之 else chart[i][j] = max(chart[i][j-1], chart[i-1][j]);//分而治之 } } return chart[len2][len1];}int main(){ cout << "enter two strings" << endl; string s1, s2; while(cin >> s1 >> s2){ cout << "【遞歸： " << LCS_Recur(s1, s2) << "】" << endl; cout << "【動歸： " << LCS_DP(s1, s2) << "】" << endl; } return 0;}