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(""); }