Suffix-array

接尾辞配列というのを使うと文字列検索でいろいろできるらしいので書いてみた
何も見ずに書くと蟻本のコードと比較したとき自分のコードがいかにぐちゃぐちゃか思い知らされる．

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int MAXN = 100000;
const int LOGN = 25;
typedef pair<int, int> P;
typedef pair<P, int> Pi;
#define fst first
#define snd second
#define num1 first.first
#define num2 first.second
#define idx second
int N;
char str[MAXN];
Pi suffix[LOGN][MAXN];
void compute_suffix_array(){
	vector< pair<char, int> > str_;
	for(int i = 0; i < N; i++)
		str_.push_back(make_pair(str[i],i));
	sort(str_.begin(),str_.end());
	for(int i = 0; i < N; i++){
		if(i != 0 && str_[i].fst == str_[i-1].fst) //前の文字と同じだったら同じ優先度をつける
			suffix[0][i] = Pi( P(suffix[0][i-1].num1, 0), str_[i].idx );
		else //異なれば低い優先度をつける
			suffix[0][i] = Pi( P(i, 0), str_[i].idx );
	}

	int k = 1, N_;
	for(N_ = 1; N_ < N; N_ *= 2);
	int pointer[2*N_]; //文字列でi番目の文字がsuffix配列でどこにあるか
	//pointer[]を初期化
	fill(pointer,pointer+2*N_,-1);
	for(int i = 0; i < N; i++)
		pointer[suffix[0][i].idx] = i;

	for(int t=1; t<=N_; t*=2,k++){
		for(int i=0; i<N; i++){
			int p = pointer[i], q = pointer[i+t];
			if(q != -1)
				suffix[k][i] = Pi( P(suffix[k-1][p].num1, suffix[k-1][q].num1), suffix[k-1][p].idx);
			else
				suffix[k][i] = Pi( P(suffix[k-1][p].num1, -1), suffix[k-1][p].idx);
		}
		sort(suffix[k], suffix[k] + N);
		puts("");
		for(int i = 0; i < N; i++)
			printf("num1=%d num2=%d idx=%d str(%d):%s\n", suffix[k][i].num1,suffix[k][i].num2,suffix[k][i].idx,t,str + suffix[k][i].idx);
		puts("");
		int rank[N];
		for(int i = 0; i < N; i++){
			if(i != 0 && suffix[k][i].fst == suffix[k][i-1].fst) //前と同じだったら同じ優先度をつける
				rank[i] = rank[i-1];
			else //異なれば低い優先度をつける
				rank[i] = i;
		}
		for(int i = 0; i < N; i++){
			//優先度をsuffix配列に反映させる
			suffix[k][i].num1 = rank[i];
			//pointer[]の作り直し
			pointer[suffix[k][i].idx] = i;
		}
	}
}

int main(){
	scanf("%s", str);
	N = strlen(str);
	compute_suffix_array();
}