Effective implementation of algorithms (Master Thesis)
Effective and error-free implementation of algorithms
src/strings/lcs/lcs.h
Go to the documentation of this file.
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
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Defines