登录后台

还没有账号?注册一个吧(>ω・*)ノ

页面导航

本文编写于 91 天前,最后修改于 91 天前,其中某些信息可能已经过时。

参照 OI-Wiki 以及 ZJK /se

后缀数组学习笔记

后缀数组(Suffix Array,简称SA)是一种不管学多少次都不会的用来处理一些字符串问题的数组。

由名字不难知道,这个东西和字符串的后缀有关。

后缀在本文中,对于一个字符串 $s[1...n]$,我们规定对于 $\forall x \in [1,n]$,$s[x...n]$ 是 $s$ 的一个后缀(Suffix)

为了简略,下文中我们用 “后缀 $x$” 代替 $s[x...n]$。

What is SA?

后缀数组一般是两个数组 $sa$ 和 $rk$。

$sa[i]$ :将一个字符串的所有后缀 按字典序 升序排序之后,排名为 $i$ 的后缀的起始位置。

$rk[i]$:将一个字符串的所有后缀 按字典序 升序排序之后,后缀 $i$ 的排名。

所以可以理解为这两个数组是双射的。并且显然,$sa[rk[i]]=rk[sa[i]]=i$。

后缀数组图例(From OI-Wiki):

How to calculate SA?


版权属于:Crab_Dave

转载时须注明出处及本声明