C++14(g++5.4) 解法, 执行用时: 1238ms, 内存消耗: 10724K, 提交时间: 2020-06-02 23:14:01

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
const int N=3e5+10,base=131;
char str[N];
ll h[N],p[N]; 
int sa[N],heigh[N],n;
ll get(int l,int r)
{
	return h[r]-h[l-1]*p[r-l+1];
}
int get_max(int a,int b)
{
	int l=0,r=min(n-a+1,n-b+1);
	while(l<r)
	{
		int mid=l+r+1>>1;
		if(get(a,a+mid-1)!=get(b,b+mid-1))r=mid-1;
		else l=mid;
	}
	return l;
}
bool cmp(int a,int b){
	int l=get_max(a,b);
	int av=a+l>n?INT_MIN:str[a+l];
	int bv=b+l>n?INT_MIN:str[b+l];
	return av<bv; 
}
int main()
{
	scanf("%s",str+1);
	n=strlen(str+1);
	p[0]=1;
	for(int i=1;i<=n;i++)
	{
		h[i]=h[i-1]*base+str[i]-'a'+1;
		p[i]=p[i-1]*base;
		sa[i]=i;
	 } 
	 sort(sa+1,sa+1+n,cmp);
	 for(int i=1;i<=n;i++)
	 printf("%d ",sa[i]-1);
	 puts("");
	 for(int i=1;i<=n;i++)
	 {
	 	if(i==1)printf("0 ");
	 	else printf("%d ",get_max(sa[i-1],sa[i]));
	 }
	return 0;
}

C++(g++ 7.5.0) 解法, 执行用时: 759ms, 内存消耗: 11632K, 提交时间: 2023-07-27 09:38:40

#include<bits/stdc++.h>
using namespace std;
unsigned long long h[1000001],p[1000001],s[1000001];
long long len;
char str[1000001];
inline long long get(long long l,long long r){return h[r]-h[l-1]*p[r-l+1];}
inline long long check(long long a,long long b){
	long long l=0,r=len-max(a,b)+1,mid;
	while(l<r){
		mid=l+r>>1;
		if(get(a,a+mid)==get(b,b+mid))l=mid+1;
		else r=mid;
	}
	return l;
}
inline long long cmp(long long a,long long b){
	long long l=check(a,b),av=a+l>len?INT_MIN:str[a+l],bv=b+l>len?INT_MIN:str[b+l];
	return av<bv;
}
int main(){
	scanf("%s",str+1);len=strlen(str+1);p[0]=1;
	for(register int i=1;i<=len;++i)h[i]=h[i-1]*13331+str[i]-'a'+1,p[i]=p[i-1]*13331,s[i]=i;
	sort(s+1,s+len+1,cmp);
	for(register int i=1;i<=len;++i)cout<<s[i]-1<<' ';
	printf("\n0");
	for(register int i=2;i<=len;++i)cout<<' '<<check(s[i],s[i-1]);
}

C++ 解法, 执行用时: 896ms, 内存消耗: 10360K, 提交时间: 2021-12-18 15:36:26

#include<bits/stdc++.h>
using namespace std;
char str[300001];
long long h[300001],p[300001]={1};
int sa[300001],n;
long long gethash(int l, int r){return h[r]-h[l-1]*p[r-l+1];}
int sumsub(int a,int b){
    int l=0,r=min(n-a+1,n-b+1);
    while(l<r){
        int mid=(l+r+1)/2;
        if(gethash(a,a+mid-1)!=gethash(b,b+mid-1))r=mid-1;
        else l=mid;
    }
    return r;
}
bool cmp(int a,int b){
    int l=sumsub(a,b),x=a+l>n?-1e9:str[a+l],y=b+l>n?-1e9:str[b+l];
    return x<y;
}
int main() {
    scanf("%s",str+1);
    n=strlen(str+1);
    for(int i=1;i<=n;i++)h[i]=h[i-1]*131+str[i]-'a'+1,p[i]=p[i-1]*131,sa[i]=i;
    sort(sa+1,sa+n+1,cmp);
    for(int i=1;i<=n;i++)cout<<sa[i]-1<<" ";
    cout<<"\n0 ";
    for(int i=2;i<=n;i++)cout<<sumsub(sa[i],sa[i-1])<<" ";
    return 0;
}