Suffix Arrayの低速な生成
ふと思い立ってSuffix Arrayを適当に実装することにした。
wikipedia:接尾辞配列
本当はSuffix Array専用の高速な生成方法()があるのだが、今回は適当な実装なのでソートアルゴリズムを使う()。
#include <iostream> #include <iomanip> #include <string> #include <vector> #include <algorithm> template <typename Iterator1, typename Iterator2> bool string_less(Iterator1 first1, Iterator1 last1, Iterator2 first2, Iterator2 last2) { while (true) { if (first2 == last2) return false; // ? < '\0' == 0 if (first1 == last1) return true; // '\0' < ?(>'\0') == 1 if (*first1 != *first2) return *first1 < *first2; ++first1; ++first2; } } int main() { std::string str("abracadabra"); std::vector<unsigned long> ar; for (unsigned long i = 0; i < str.length(); i++) ar.push_back(i); std::sort(ar.begin(), ar.end(), [&](unsigned long a, unsigned long b)->bool { return string_less(str.begin()+a, str.end(), str.begin()+b, str.end()); } ); for (auto i : ar) { std::cout << std::setw(3) << i << " "; for (auto itr = str.begin()+i; itr != str.end(); itr++) std::cout << *itr; std::cout << std::endl; } }
せっかくなのでC++11の機能を生かそうと思ったのだが、今ひとつ活用出来ていない。気が向いたら高速なものも実装してみようと思う。