最長公共子序列問題很早就在很多論壇上見過，前幾天看到一個人發了一篇帖子，心血來潮就去看算法導論上的動態規劃部分，關於這個問題不再細述，直接貼C++實現的具體代碼了。 [cpp] //做大公共子序列問題 #pragma once #include <string> using std::string; #define OVER 1 //書中使用箭頭符號表示的，這裡用宏代替 #define LEFT 2 #define LEFTOVER 3 class LCS { private: string sX; //用於存儲子序列 string sY; int **c; //這兩個二維指針是為了維護一個動態的表格，後面會根據這個表的來遞歸生成最長公共子序列 int **b; int m; //分別表示兩個字符串的長度，為了和書上偽代碼一致就沒有改動 int n; public: LCS(); ~LCS(); void ProRun(); //只做動態規劃部分的雙重循環 void Running(); //供main()調用 void PrintResult(int ,int); //遞歸輸出 }; [cpp] #include "LCS.h" #include <iostream> #include <fstream> using namespace std; LCS::LCS() { sX = "ABCBDAB"; sY = "BDCABA"; m = sX.size(); n = sY.size(); c = new int *[m+1]; //書中是把字符所在的序號看成了下標，所以得多開辟一個空間 b = new int *[m+1]; //而且在雙重循環時會用到一個空的c[0][0]和b[0][0] for (int i = 0; i <= m; i++) { c[i] = new int[n+1]; b[i] = new int[n+1]; } for (int i = 0; i <= m; i++) { for (int j = 0; j <= n; j++) { c[i][j] = 0; //先賦值 b[i][j] = 0; } } } LCS::~LCS() { for (int i = 0; i <= m; i++) { delete c[i]; //釋放空間 delete b[i]; } delete c; delete b; } void LCS::ProRun() { //這個算法時間復雜度為O(mn) for (int i = 1; i<= m; i++) { for (int j = 1; j <= n; j++) { if (sX[i-1] == sY[j-1]) { c[i][j] = c[i-1][j-1] + 1; b[i][j] = LEFTOVER; } else if(c[i-1][j] >= c[i][j-1]) { c[i][j] = c[i-1][j]; b[i][j] = OVER; } else { c[i][j] = c[i][j-1]; b[i][j] = LEFT; } } } } void LCS::PrintResult(int i, int j) { if (i ==0 || j == 0) { return; } if (b[i][j] == LEFTOVER) { PrintResult(i-1,j-1); cout<<sX[i-1]<<endl; } else if (b[i][j] == OVER) { PrintResult(i-1, j); } else { PrintResult(i, j-1); } } void LCS::Running() { LCS::ProRun(); LCS::PrintResult(m,n); } [cpp] #include <iostream> #include "ALSPro.h" #include "LCS.h" using namespace std; void main() { //ASL as; //as.PrintResult(); LCS ls; ls.Running(); }
