Effective implementation of algorithms (Master Thesis)
Effective and error-free implementation of algorithms
|
00001 #ifndef H_STRINGS_SUFFIX_ARRAY_NAIVE_NAIVE 00002 #define H_STRINGS_SUFFIX_ARRAY_NAIVE_NAIVE 00003 00004 #include <stdio.h> 00005 #include "utils/preconditions/preconditions.h" 00006 #include <vector> 00007 #include <iterator> 00008 #include <algorithm> 00009 #include "sort_helper.h" 00010 00022 namespace strings { 00023 namespace suffix_array { 00024 00025 class NaiveSuffixArray { 00026 public: 00036 template <typename _Iterator> 00037 static void buildSuffixArray( 00038 _Iterator first, 00039 _Iterator last, 00040 std::vector<int> *out) { 00041 typename std::iterator_traits<_Iterator>::difference_type length = last - first; 00042 00043 out->resize(length); 00044 for (int i = 0; i < length; i++) { 00045 out->at(i) = i; 00046 } 00047 SortHelper<_Iterator> helper(first, last); 00048 std::sort(out->begin(), out->end(), helper); 00049 } 00050 }; 00051 00052 } // namespace suffix_array 00053 } // namespace strings 00054 00055 #endif