后缀数组

#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;

}