Effective implementation of algorithms (Master Thesis)
Effective and error-free implementation of algorithms
|
00001 #ifndef H_STRINGS_LCS_LCS 00002 #define H_STRINGS_LCS_LCS 00003 00007 #include <vector> 00008 #include <algorithm> 00009 #include "utils/preconditions/preconditions.h" 00010 #include "debug/ppdebug.h" 00011 00012 namespace strings { 00013 namespace lcs { 00014 00018 template<typename T> 00019 class LCS { 00020 public: 00029 static int length(const T* seq1, int len1, const T* seq2, int len2) { 00030 Preconditions::check(len1 >= 0); 00031 Preconditions::check(len2 >= 0); 00032 if (len1 == 0 || len2 == 0) { 00033 return 0; 00034 } 00035 std::vector<int> current(len1 + 1, 0); 00036 std::vector<int> next(len1 + 1); 00037 for (int j = 0; j < len2; j++) { 00038 // we are going to process best results for 00039 // LCS(seq1, seq2[0,j) into next[j] ) 00040 next[0] = 0; 00041 for (int i = 0; i < len1; i++) { 00042 if (seq1[i] == seq2[j]) { // match 00043 next[i + 1] = current[i] + 1; 00044 } else { // take the best of previous values 00045 next[i + 1] = std::max(current[i + 1], next[i]); 00046 } 00047 } 00048 current.swap(next); // advance by 1 line 00049 } 00050 00051 return current[len1]; 00052 }; 00053 00064 static int subsequence(const T* seq1, int len1, const T* seq2, int len2, 00065 std::vector<T>* out) { 00066 Preconditions::check(len1 >= 0); 00067 Preconditions::check(len2 >= 0); 00068 out->clear(); 00069 if (len1 == 0 || len2 == 0) { 00070 return 0; 00071 } 00072 00073 // length[i][j] is length of the LCS of 00074 // seq1[0..i) and seq2[0..j) 00075 std::vector<std::vector<int> > length(len1 + 1); 00076 std::vector<std::vector<bool> > prev(len1 + 1); 00077 // Initialize first row 00078 length[0].resize(len2 + 1, 0); 00079 prev[0].resize(len2 + 1); 00080 00081 for (int i = 0; i < len1; i++) { 00082 length[i].resize(len2 + 1, 0); 00083 prev[i].resize(len2 + 1); 00084 00085 for (int j = 0; j < len2; i++) { 00086 if (seq1[i] == seq2[j]) { // match 00087 length[i + 1][j + 1] == length[i][j] + 1; 00088 } else { // take the best of previous values 00089 if (length[i][j + 1] > length[i+1][j]) { 00090 length[i+1][j+1] = length[i][j+1]; 00091 prev[i+1][j+1] = false; 00092 } else { 00093 length[i+1][j+1] = length[i+1][j]; 00094 prev[i+1][j+1] = true; 00095 } 00096 } 00097 } 00098 } 00099 00100 // construct the sequence in reverse order 00101 int i = len1; 00102 int j = len2; 00103 while (i > 0 && j > 0) { 00104 if (seq1[i - 1] == seq2[j - 1]) { 00105 out->push_back(seq1[i - 1]); 00106 } else { 00107 if (prev[i][j]) { 00108 j--; 00109 } else { 00110 i--; 00111 } 00112 } 00113 } 00114 // length[] should be consistent with output itself 00115 assert(out->size() == length[len1][len2]); 00116 00117 std::reverse(out->begin(), out->end()); 00118 return out->size(); 00119 } 00120 }; 00121 00122 } // namespace lcs 00123 } // namespace strings 00124 #endif