#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;
}
}
}
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<string>
using namespace std;
char x[100111];
int sa[100111]={0};
int rank[100111];
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 n;
int find(char *p){
int m = strlen(p);
if (strncmp(p, x + sa[0], m) < 0 || strncmp(p, x + sa[n-1], m) > 0) return -1;
int L = 0, R = n-1;
while (R >= L){
int M = L + (R - L) / 2;
int res = strncmp(p, x + sa[M], m);
if (res == 0) return M;
if (res < 0) R = M - 1; else L = M + 1;
}
return -1;
}
int height[100111];
void GetHeight(){
int k = 0, i, j;
for (i = 1; i < n; i++){
if (k) k--;
int j = sa[rank[i] - 1];
while (x[i+k] == x[j+k]) k++;
height[rank[i]] = k;
}
for (int i = 1; i < n; i++) cout<<height[i]<<' ';
}
int main(){
ios::sync_with_stdio(false);
cin>>x;
n = strlen(x);
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 = -1;
for (int i = 0; i < n; i++){
if (i && q[i].first == q[i-1].first && q[i].second == q[i-1].second )
rank[q[i].i] = rank[q[i-1].i];
else rank[q[i].i] = ++cnt;
}
// for (int i = 0; i < n; i++) cout<<rank[i]<<' ';
// cout<<endl;
if (cnt >= n || k * 2 > n) break;
for (int i = 0; i < n-k; i++) {
q[i].first = rank[i];
q[i].second = rank[i + k];
q[i].i = i;
}
for (int i = n-k; i < n; i++){
q[i].first = rank[i];
q[i].second = 0;
q[i].i = i;
}
}
for (int i = 0; i < n; i++) sa[rank[i]] = i;
for (int i = 0; i < n; i++) cout<<sa[i]<<' ';
cout<<'\n';
GetHeight();
return 0;
}
相关资源：七夕情人节表白HTML源码(两款)
