P10469 后缀数组（Hash+二分）

#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef vector<string> VS;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
inline int log_2(int x) {return 31-__builtin_clz(x);}
inline int popcount(int x) {return __builtin_popcount(x);}
inline int lowbit(int x) {return x&-x;}
const ull P=131,N=3e5+3;//根据经验进制P取为131不易冲突
ull h[N],p[N];//ull相当于一个数对2^64取模,p数组里存的是进制次幂运算预处理的结果
char ch[N];
int SA[N];
int n;
ull _hash(int l,int r)
{
    return h[r]-h[l-1]*p[r-l+1];//处理h数组时将第一位字符作为最高位处理
    //故此时要运算出h[r]-h[l-1]的哈希值需要将h[l-1]乘P的r-l+1次
}
void init()
{
	h[0]=0,p[0]=1;
    for(int i=1;i<=n;++i)
    {
        h[i]=h[i-1]*P+ch[i];//用的是ascii码参与运算
        p[i]=p[i-1]*P;
    }
}

int find_pos(int x,int y)
{
	//返回相同的最大长度
	auto check = [&](int M)->bool
	{
		if(!M) return true;
		if(x+M-1>n||y+M-1>n) return false;
		return _hash(x,x+M-1)==_hash(y,y+M-1);
	};
	int L = 0, R = min(n-x+1,n-y+1)+1;
	while(L+1<R)
	{
		int M = (L+R)/2;
		if(check(M)) L = M;
		else R = M;
	}
	return L;	
}
bool cmp(int x,int y)
{
	int pos = find_pos(x,y);
	return ch[x+pos] < ch[y+pos];
}
void solve()
{
	scanf("%s",ch+1);
	n = strlen(ch+1);
	init();
	for(int i=1;i<=n;++i) SA[i] = i;
	sort(SA+1,SA+1+n,cmp);
	for(int i=1;i<=n;++i) cout<<SA[i]-1<<" \n"[i==n];
	cout<<"0 ";
	for(int i=2;i<=n;++i) cout<<find_pos(SA[i],SA[i-1])<<" ";
}
int main()
{
	int T = 1;
	//cin>>T;
	while(T--)
	{
		solve();
	}
}