meryngii.neta

今日も新たな"ネタ"を求めて。

Suffix Arrayの低速な生成

ふと思い立ってSuffix Arrayを適当に実装することにした。
wikipedia:接尾辞配列
本当はSuffix Array専用の高速な生成方法(O(n log n))があるのだが、今回は適当な実装なのでソートアルゴリズムを使う(O(n^2 log n))。

#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の機能を生かそうと思ったのだが、今ひとつ活用出来ていない。気が向いたら高速なものも実装してみようと思う。