Effective implementation of algorithms (Master Thesis)
Effective and error-free implementation of algorithms
|
00001 #ifndef H_STRINGS_SUFFIX_ARRAY_LCP_NAIVE 00002 #define H_STRINGS_SUFFIX_ARRAY_LCP_NAIVE 00003 #include "utils/preconditions/preconditions.h" 00004 namespace strings { 00005 namespace suffix_array { 00006 00015 class LCPNaive { 00016 private: 00017 template<typename _Iterator> 00018 static inline int lcp(_Iterator pos1, _Iterator pos2, _Iterator last) 00019 { 00020 int i = 0; 00021 while (pos1 != last && pos2 != last && *pos1 == *pos2) { 00022 ++i; 00023 ++pos1; 00024 ++pos2; 00025 } 00026 return i; 00027 } 00028 00029 public: 00037 template<typename _Iterator, typename _SAIterator> 00038 static void getHeightArray(_Iterator seq_first, _Iterator seq_last, 00039 _SAIterator sa_first, _SAIterator sa_last, 00040 std::vector<int> * out) 00041 { 00042 Preconditions::checkNotNull(out); 00043 00044 Preconditions::check(seq_last - seq_first == sa_last - sa_first); 00045 00046 unsigned int n = sa_last - sa_first; 00047 00048 out->clear(); 00049 out->resize(n); 00050 00051 const int undefined = 0; 00052 (*out)[0] = undefined; 00053 00054 for (unsigned int i = 1; i < n; i++) { 00055 _Iterator pos1 = seq_first + *(sa_first + (i - 1)); 00056 _Iterator pos2 = seq_first + *(sa_first + i); 00057 (*out)[i] = lcp(pos1, pos2, seq_last); 00058 } 00059 } 00060 }; 00061 00062 } // namespace suffix_array 00063 } // namespace strings 00064 #endif