后缀数组学习笔记

lizhous · 2023-02-03 09:42:36 · 个人记录

概念

后缀数组，即对于一个串，它的每个后缀按字典序排序后得到的数组。

有两个数组要求：

朴素

sort排序一下

优化

倍增优化：我们进行 \log n 次排序，第 k 次取所有后缀的前 2^k 个字符进行排序。若上次排序第 i 为开头的后缀排名为 rkl_i（可并列），那假如这次需要比较以 i 开头的串与以 j 开头的串，只需要先比较 rkl_i 与 rkl_j，若相等再比较 rkl_i+2^{k-1} 与 rkl_j+2^{k-1} 即可。显然这样是正确的。

#include<iostream> 
#include<cstdio>
#include<algorithm>
#include<cstring>
#define int long long
using namespace std;
char a[1000005];
int sa[1000005],rk[1000005],tmp[1000005];
int k,n;
inline bool cmp(int x,int y)
{
    if(rk[x]==rk[y])
    {
        int i=(x+k<=n?rk[x+k]:-1);
        int j=(y+k<=n?rk[y+k]:-1);
        return i<j;
    }
    return rk[x]<rk[y];
}
void GetSark()
{
    for(int i=1;i<=n;i++)
    {
        sa[i]=i;
        rk[i]=a[i]+1;
    }
    for(int i=1;i<=n;i=i*2)
    {
        k=i;
        sort(sa+1,sa+n+1,cmp);
        for(int z=1;z<=n;z++)
        {
            tmp[sa[z]]=tmp[sa[z-1]]+(cmp(sa[z-1],sa[z])?1:0);
        }
        for(int z=1;z<=n;z++)
        {
            rk[z]=tmp[z];
        }
    }
}
signed main()
{
    cin>>a+1;
    n=strlen(a+1);
    GetSark();
    for(int i=1;i<=n;i++)
    {
        cout<<sa[i]<<' '<<rk[i]<<endl;
    }
} 

应用

在字符串 S 中找字符串 T

二分排名即可

bool find(string S,string T)
{
    int l=0,r=S.size(),ans;
    while(l<=r)
    {
        int mid=r+l>>1;
        if(S.compare(sa[mid],T.size(),T)==-1)
        {
            l=mid+1;
        }
        else
        {
            ans=mid;
            r=mid-1;
        }
    }
    return S.compare(sa[ans],T.size(),T)==0;
}

LCP

LCP即最长公共前缀

SA排完序后，有：

1. lcp(i,j)=\min(lcp(i,k),lcp(k,j))(1 \le i \le k \le j)
2. lcp(i,j)=\min(lcp(k,k-1))(1 \le i < k \le j)

height

后缀数组的另一应用

则 O(n) 扫一扫就可以了

void get_height()
{
    int k=0;
    for(int i=1;i<=a.size();i++)
    {
        if(k)
        {
            k--;
        }
        int j=sa[rk[i]-1];
        while(a[i+k]==a[j+k]) k++;
        height[rk[i]]=k;
    }
}