题目描述

后缀数组 (SA) 是一种重要的数据结构，通常使用倍增或者DC3算法实现，这超出了我们的讨论范围。

在本题中，我们希望使用快排、Hash与二分实现一个简单的O($nlog^2n$)的后缀数组求法。

详细地说，给定一个长度为 n 的字符串S（下标 0~n-1），我们可以用整数 k($0 \le k<n$) 表示字符串S的后缀 S(k~n-1)。

把字符串S的所有后缀按照字典序排列，排名为 i 的后缀记为 SA[i]。

额外地，我们考虑排名为 i 的后缀与排名为 i-1 的后缀，把二者的最长公共前缀的长度记为 Height[i]。

我们的任务就是求出SA与Height这两个数组

样例

输入

ponoiiipoi

输出

9 4 5 6 2 8 3 1 7 0
0 1 2 1 0 0 2 1 0 2

算法

字符串Hash + 二分

具体思路见进阶指南及代码注释

C++ AC代码

#include <bits/stdc++.h>
using namespace std;
#define ULL unsigned long long
const int P=1331;

char x[300010];     //原字符串 
int sa[300010];     // sa ->> SA
ULL p[300010];      //p[x] ->> P^x
ULL H[300010];      //Hash
int n;              //字符个数 

ULL find(int a,int b);      //返回x[a~b]之间的hash值 
int len(int a,int b);       //返回x[a~n-1]与x[b~n-1]的最长公共前缀的长度
bool cmp(int a,int b);      //伪函数 

int main()
{
    cin>>x;
    n=strlen(x);
    p[0]=1;                         //sa[0]就是0不用管 
    H[0]=x[0]-'a'+1;                
    for(int i=1;i<n;i++)            //直接从0开始的话 H，p会越界 
    {                                
        sa[i]=i;    
        p[i]=p[i-1]*P;              //求p^n 
        H[i]=H[i-1]*P+x[i]-'a'+1;   //求hash值 
    }
    sort(sa,sa+n,cmp);              //利用cmp直接sort即可(但你想手写快排也没人拦你)
    for(int i=0;i<n;i++)
        cout<<sa[i]<<" ";
    cout<<endl;
    cout<<0<<" ";                       //直接输出height[1] 
    for(int i=1;i<n;i++)                //从0开始的话又会越界...... 
        cout<<len(sa[i],sa[i-1])<<" ";  //反正又不是真的写后缀数组求到了就直接输出即可 
    return 0;
}

ULL find(int a,int b)
{
    return (H[b]-H[a-1]*p[b-a+1]);
}


int len(int a,int b)
{
    if(x[a]!=x[b])          //由于len函数返回的是x[a]加上x[a]与x[b]后面相同的长度 (返回值最小为1)
        return 0;           //所以当x[a]与x[b]不等时,直接返回0  
    int l=0;
    int r=n-1-max(a,b);
    while(l<r)          //二分
    {
        int mid=(l+r+1)/2;
        if(find(a,a+mid)==find(b,b+mid)&&a+mid<n&&b+mid<n)
            l=mid;
        else
            r=mid-1;
    }
    return l+1;             //千万记得要加一 
}

bool cmp(int a,int b)
{
    int l=len(a,b);
    return x[a+l]<x[b+l];
//事实上是 x[(a+l-1)+1] < ~~~~~~
}