LCS.rar_LCS_lcs matlab_最长公共子序列

#include <iostream> #include <string> #include <vector> using namespace std; /* class : LCS descript : compute the maximum common length between the two strings. Note : Histor : */ #define L(i,j) m_lens[(i)*(N+1)+j] class LCS { public: LCS(const string &, const string &); ~LCS(); int GetLength() const; string GetCommon() const; // dynamic programming void Compute(); // recursive method void ComputeRecursive() { if(hasComputed) return; for(int i=0; i<=M; i++) { for(int j=0; j<=N; j++) { L(i,j) = -1; } } for(int i=0; i<=M; i++) L(i, 0) = 0; for(int i=0; i<=N; i++) L(0, i) = 0; max_len(M, N); hasComputed = true; } private: // 迭代法计算S1[0...m-1], s2[0..n-1]之间的子串 int max_len(int m, int n) { if(L(m,n) >= 0) return L(m, n); if(s1[m-1] == s2[n-1]) { L(m,n) = 1+max_len(m-1, n-1); } else if(max_len(m-1, n) > max_len(m, n-1)) { L(m, n) = max_len(m-1, n); } else L(m, n) = max_len(m, n-1); } LCS(); LCS(const LCS &); LCS & operator =(const LCS &); bool hasComputed; int M,N; string s1; string s2; int *m_lens; }; string LCS::GetCommon() const { char * commStr = new char[L(M,N) + 1]; commStr[L(M,N)] = '\0'; vector<char> reversedCommon; // save common string , but reversed int i = M; int j = N; int k = L(M,N)-1; while(i>0 & j> 0) { if(L(i,j) > L(i-1, j) && L(i,j) > L(i, j-1)) { commStr[k--] = s1[i-1]; //reversedCommon.push_back(s1[i-1]); i--; j--; } else if(L(i,j) > L(i-1, j)) j--; else i--; } string toret(commStr); delete commStr; return toret; } int LCS::GetLength() const { if(!hasComputed) return -1; return L(M, N); } // compute the two strings void LCS::Compute() { if(hasComputed) return; for(int i=1; i<=M; i++) { for(int j=1; j<=N; j++) { if(s1[i-1] == s2[j-1]) { L(i,j) = L(i-1, j-1) + 1; } else if(L(i-1,j) > L(i, j-1)) { L(i,j) = L(i-1, j); } else { L(i,j) = L(i, j-1); } } } hasComputed = true; } // constructor LCS::LCS(const string &s1, const string &s2) { M = s1.length(); N = s2.length(); hasComputed = false; this->s1 = s1; this->s2 = s2; m_lens = new int[(M+1)*(N+1)]; memset(m_lens, 0, sizeof(int)*(M+1)*(N+1)); } // destructor LCS::~LCS() { delete m_lens; } int main() { LCS lcs("ABCBDAB", "BDCABA"); //lcs.Compute(); lcs.ComputeRecursive(); cout<<lcs.GetLength()<<endl; cout<<lcs.GetCommon()<<endl; return 0; }