后缀数组

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e6+10;
static const int N = 1e6 + 10;
int num = 128, len;
string s;
int fir[N], sec[N], t[N];
int sa[N];      //第 i 个后缀字符串按字典序排列为 sa[i];
int sa_1[N];    //表示排列在第 i 位的字符串为sa_1[i];
int lcp[N];		//sa_1 的公共前缀lcp[i] = 最大公共前缀(sa_1[i],sa_1[i+1])
void A(){
	memset(fir,0,sizeof(fir));
	memset(sec,0,sizeof(sec));
	memset(t,0,sizeof(t));
	memset(sa,0,sizeof(sa));
	memset(sa_1,0,sizeof(sa_1));
}
void run() {   //求 sa 以及 sa_1
	len = s.size();
    for (int i = 1; i <= num; ++i) t[i] = 0; 
	for (int i = 1; i <= len; ++i) ++t[fir[i] = s[i-1]];
	for (int i = 1; i <= num; ++i) t[i] += t[i - 1];
	for (int i = len; i >= 1; --i) sa[t[fir[i]]--] = i;	
	for (long long int k = 1; k <= len; k <<= 1) {
		int cnt = 0;
		for (int i = len - k + 1; i <= len; ++i) sec[++cnt] = i;
		for (int i = 1; i <= len; ++i) if (sa[i] > k) sec[++cnt] = sa[i] - k;
		for (int i = 1; i <= num; ++i) t[i] = 0;
		for (int i = 1; i <= len; ++i) ++t[fir[i]];
		for (int i = 1; i <= num; ++i) t[i] += t[i - 1];
		for (int i = len; i >= 1; --i) sa[t[fir[sec[i]]]--] = sec[i], sec[i] = 0;
		swap(fir, sec);
		fir[sa[1]] = 1, cnt = 1;
		for (int i = 2; i <= len; ++i) 
			fir[sa[i]] = (sec[sa[i]] == sec[sa[i - 1]] && sec[sa[i] + k] == sec[sa[i - 1] + k]) ? cnt : ++cnt;
		if (cnt == len) break;
		num = cnt;
	}
	for(int i=1;i<=len;i++){
		sa_1[sa[i]]=i;
	}
	swap(sa,sa_1);
	//for(int i=1;i<=len;i++)cout<<sa[i]<<" ";cout<<endl;
}

/*********************线段树**********************/
int shu[N*2];
int n;    //1~~n
//st=1,en=n,node=1;
void built(int node,int st,int en){
    int mod=(st+en)/2;
    if(st==en){
        shu[node]=lcp[st];
        return ;
    }
    built(node*2,st,mod);built(node*2+1,mod+1,en);
    shu[node]=min(shu[node*2+1],shu[node*2]);
}
int query(int node,int st,int en,int l,int r){   //求和（l~~r),st=1,en=n
 
    if(r<st||l>en)return 0;
    if(l<=st&&en<=r)return shu[node];
    int mod=(st+en)/2;
    return min(query(2*node,st,mod,l,r),query(2*node+1,mod+1,en,l,r));
 
}
/*******************************************/
int soul(int x,int y,int z){
	z--;
	z=min(z,0);
	x+=z;y+=z;
	while(x<=len&&y<=len&&s[x]==s[y]){x++;y++;z++;}
	return z;
}
void lce(){   //求 lcp
	for(int i=1;i<len;i++){
		lcp[i]=soul(i,i+1,lcp[i-1]);
	}
	built(1,1,len);
}
int add_211(int l,int r){   //求第 l 个和第 r 个后缀字符串的最长公共前缀。
	l = sa[l];
	r = sa[r];
	return query(1,1,len,l,r);
}
int main(){
	
	cin>>s;
	run();
	//lce();
	for(int i=1;i<=len;i++)cout<<sa_1[i]<<" ";cout<<endl;
	//for(int i=1;i<=s.size();i++)cout<<sa_1[i]<<" ";cout<<"\n";
	return 0;
}