21
后缀数组
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<string>
using namespace std;
string x;
int sa[1111]={0}, ch[33] = {0};
int d[2777][2777] = {0}, last = 0;
struct data{
int first, second, i;
friend bool operator <(data a, data b){
if (a.first != b.first) return a.first < b.first;
return a.second < b.second;
}
}q[1111];
int main(){
cin>>x;
int n = x.length();
for (int i = 0; i < n-1; i++){
q[i].first= x[i];
q[i].second = x[i+1];
q[i].i = i;
} q[n-1].first= x[n-1]; q[n-1].second = 0; q[n-1].i = n-1;
for (int k = 2; k <= n; k <<= 1){
sort(q, q + n);
int cnt = 0;
for (int i = 0; i < n; i++){
if (i && q[i].first == q[i-1].first && q[i].second == q[i-1].second )
sa[q[i].i] = sa[q[i-1].i];
else sa[q[i].i] = ++cnt;
}
for (int i = 0; i < n; i++) cout<<sa[i]<<' ';
cout<<endl;
if (cnt >= n || k * 2 > n) break;
for (int i = 0; i < n-k; i++) {
q[i].first = sa[i];
q[i].second = sa[i + k];
q[i].i = i;
}
for (int i = n-k; i < n; i++){
q[i].first = sa[i];
q[i].second = 0;
q[i].i = i;
}
}
}最后更新：2017-08-23 00:02:28