SA-ISを実装した

https://local.ugene.unipro.ru/tracker/secure/attachment/12144/Linear+Suffix+Array+Construction+by+Almost+Pure+Induced-Sorting.pdf を読んで実装した。
まだverifyしていないので正しいか知らない。
[追記4/28]
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1620 でverifyしました
[さらに追記]
verifyは通ったけど実は微妙にバグっているかもしれないことが判明した

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;

// SAIS(s,n)
// s is a string; n is the length of s (except null character)
// return SA of s
const bool typeS = true;
const bool typeL = false;
vector<int> SAIS(char *s, int n){
    n++;
    //count[i] := the number of characters whose Ascii code are i
    int count[256];
    memset(count, 0, sizeof(int)*256);
    for(int i=0;i<n;i++){ count[s[i]]++; }
    //Step 1
    //determine type and LMS
    vector<int> LMS;
    bool *t = new bool[n];
    t[n-1] = typeS;
    for(int i = n-2; i >= 0; i--){
        if(s[i] > s[i+1]){
            t[i] = typeL;
            if(t[i+1] == typeS)
                LMS.push_back(i+1);
        }else if(s[i] < s[i+1]){
            t[i] = typeS;
        }else{
            t[i] = t[i+1];
        }
    }
    //construct buckets
    vector<unsigned char> bucket;
    char char2bucketIdx[256];
    for(int c=0;c<256;c++){
        if(count[c] > 0){
            bucket.push_back(c);
            char2bucketIdx[c] = bucket.size()-1;
        }
    }
    //put LMS into bucket
    vector<int> SA(n);
    fill(SA.begin(), SA.end(), -1);
    int *index = new int[bucket.size()];
    index[0] = 1;
    for(int b = 1; b < bucket.size(); b++){ index[b]=index[b-1]+count[bucket[b]]; }
    for(int l = LMS.size()-1; l >= 0; l--){
        int i = LMS[l];
        int idx = char2bucketIdx[ s[i] ];
        SA[index[idx]-1] = i;
        index[idx]--;
    }
    //Step2
    //scan from left to right and determine SA of typeL-substrings
    index[0] = 0;
    for(int b = 1; b < bucket.size(); b++){ index[b]=index[b-1]+count[bucket[b-1]]; }
    for(int i = 0; i < n; i++){
        int j = SA[i];
        if(j <= 0) continue;
        if(t[j-1] == typeL){
            int k = char2bucketIdx[s[j-1]];
            SA[index[k]] = j-1;
            index[k]++;

        }
    }
    //Step3
    //scan from left to right and determine SA of typeS-substring
    index[0] = 1;
    for(int b = 1; b < bucket.size(); b++){ index[b]=index[b-1]+count[bucket[b]]; }
    for(int i = n-1; i>=0; i--){
        int j = SA[i];
        if(j <= 0) continue;
        if(t[j-1] == typeS){
            int k = char2bucketIdx[s[j-1]];
            SA[index[k]-1] = j-1;
            index[k]--;
        }
    }

    return SA;
}

int main(){
    char s[] = "mmiissiissiippii";
    vector<int> SA = SAIS(s,16);
    for(int i = 0; i < SA.size(); i++){
        printf("%d ", SA[i]);
    }
    puts("");
}