---
title: "后缀数组"
created: 2025-11-28
tags:
  - 算法
---

# 后缀数组

## 题目 [后缀数组](https://www.acwing.com/problem/content/142/)

![[image-900729e6.png]]

## 思路分析

题意比较复杂

找到所有的后缀数组 然后按字典序排序 再比较得出两个相邻的最长公共前缀

最长公共前缀可能会想到用trie写 但是第一步有些似曾相识 如果用trie的话 又得把所有的后缀子串全都存一遍进去

考虑到这么复杂的操作 还是用字符串哈希来得快

所谓后缀数组

后缀不需要全存下来 只需要存第一个元素的指针即可

ponoiiipoi

10 i

9 oi

8 poi

7 ipoi

6 iipoi

5 iiipoi

4 oiiipoi

3 noiiipoi

2 onoiiipoi

1 ponoiiipoi

排序后得到 10 5 6 7……

再计算相邻的最长公共前缀 得到 0 1 2 1 0 0……

之前字典序排序用的是先求出最小表示法 但用字符串哈希了就没必要这样麻烦了

字典序排序不外乎就是一个字母一个字母比较 看第一个不一样的字母哪个更小就排前面

这个其实就是第三步也要做的——找最长公共前缀

找到最长公共前缀可以用二分 跟上题差不多思路 枚举下标 二分长度

找到最大公共前缀后 比较下一个元素的值 即可作排序

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

typedef unsigned long long ULL;

const int N=300010,P=131;

char str[N];

ULL h[N],p[N];

int sa[N];

int n;

ULL find(int l,int r){

    return h[r]-h[l-1]*p[r-l+1];

}

int get_MaxPreCommon(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(find(a,a+mid-1) == find(b,b+mid-1))

            l=mid;

        else

            r=mid-1;

    }

    return r;

}

bool cmp(int a,int b){

    int l=get_MaxPreCommon(a,b);

    int anv=a+l>n ? INT_MIN : str[a+l];

    int bnv=b+l>n? INT_MIN : str[b+l];

    return anv<bnv;

}

int main()

{

    cin>>str+1;

    n=strlen(str+1);

    p[0]=1;

    for(int i=1;i<=n;i++){

        h[i]=h[i-1]*P+str[i];

        p[i]=p[i-1]*P;

        sa[i]=i;

    }

    sort(sa+1,sa+1+n,cmp);

    for(int i=1;i<=n;i++)

        cout<<sa[i]-1<<" ";

    cout<<endl;

    for(int i=1;i<=n;i++)

    {

        if(i==1)

            cout<<"0 ";

        else

            cout<<get_MaxPreCommon(sa[i-1],sa[i])<<" ";

    }

    return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[兔子与兔子|兔子与兔子]] 🏠 [[00-刷题理模型]] ➡️ [[回文串的最大长度|回文串的最大长度]]