首页 > 其他分享 >[学习笔记]后缀数组(Suffix Array)

[学习笔记]后缀数组(Suffix Array)

时间:2024-08-05 12:05:57浏览次数:14  
标签:字符 Suffix 后缀 复杂度 关键字 Array 排序 log

后缀数组(suffix array)是一个通过对字符串的所有后缀经过排序后得到的数组。后缀数组被 Manber 和 Myers 于1990年提出, 作为对后缀树的一种替代, 更简单以及节省空间。它们也被Gaston Gonnet 于1987年独立发现, 并命名为“PAT数组”。

后缀数组有很多奇妙的性质, 这些性质可以帮助解决很多字符串问题(然后出串串题虐死别人)

板子题:

P3809 【模板】后缀排序

\(O(n \log^2 n)\) 做法

后缀 \(i\) 代指以第 \(i\) 个字符开头的后缀, 也称 \(suff(i)\), 本文规定字符串下标从 \(1\) 开始, 后文都将使用数组式下标。

首先朴素的想, 将 \(n\) 个后缀直接塞进 string 数组内大力 sort, 很不幸 STL 提供的 string 类型比较字典序的复杂度为 \(O(n)\), 我们只能得到 \(O(n^2 \log n)\) 的暴力。

回想一下我们比较字符串的字典序的过程:

1.从第一个字符开始比较。

2.如果当前字符不相等,就直接比较这两个字符,即可得出答案。

3.否则,继续比较下一个字符。

这个过程实际上就是在寻找两个字符串的最长公共前缀,而下一个字符就一定不相等。最长公共前缀是具有单调性的,哈希上二分一下就能 \(O(\log n)\) 比较字典序,这样我们的算法就优化到了 \(O(n \log^2 n)\)。这个复杂度已经可以通过洛谷的模板题了(代码)。

复杂度瓶颈在排序和求 \(LCP\), 不好优化, 考虑另一种 \(O(n \log^2 n)\) 的做法:

先按照每个后缀的第一个字符排序。对于每个字符,我们按照字典序给一个排名(当然可以并列), 这里称作关键字。

接下来我们再把相邻的两个关键字合并到一起,就相当于根据每一个后缀的前两个字符进行排序。想想看,这样就是以第一个字符(也就是自己本身)的排名为第一关键字,以第二个字符的排名为第二关键字,把组成的新数排完序之后再次标号。没有第二关键字的补零。

既然是倍增,就要有点倍增的样子。接下来我们对于一个在第 \(i\) 位上的关键字,它的第二关键字就是第 \(i+2\) 位置上的,联想一下,因为现在第 \(i\) 位上的关键字是 \(suff(i)\) 的前两个字符的排名,第 \(i+2\) 位置上的关键字是 \(suff(i+2)\) 的前两个字符的排名,这两个一合并,不就是 \(suff(i)\) 的前四个字符的排名吗?方法同上,排序之后重新标号,没有第二关键字的补零。同理我们可以证明,下一次我们要合并的是第 i 位和第 i+4 位,以此类推即可……

那么我们什么时候结束呢?很简单,当所有的排名都不同的时候我们直接退出就可以了,因为已经排好了。最多倍增 \(O(\log n)\) 次,使用 sort 排序,总复杂度 \(O(n \log^2 n)\)。

这种方法的常数远小于上一种方法, 因为倍增中每次排序都会使后缀数组更有序, sort 越有序跑得越快, 有序后可以提前退出, 所以跑不满 O(n \log^2 n) (代码)。

\(O(n \log n)\) 做法

复杂度还是一样, 复杂度瓶颈是倍增和排序好像也没啥变化, 除了常数变小, 这种做法还有什么好处吗?

当然有!排序的关键字变为了上一次排序的排名, 排名是 \(O(n)\) 的, 聪明的同学们应该立刻想到计数排序。关键字有两个也好办, 多关键字计数排序就是基数排序, 常数个关键字的基数排序时间复杂度还是 \(O(n)\), 排序两次就成了。

因为两次计数排序需要很多转换, 代码里很多层循环, 总复杂度是常数略大的 \(O(n \log n)\), 并没有与上面的小常数 \(O(n \log^2 n)\) 拉开太大差距。

\(O(n)\) 做法

还没有学,先在这里挖个坑,以后学了再补。

参考:

洛谷题解

oiwiki

标签:字符,Suffix,后缀,复杂度,关键字,Array,排序,log
From: https://www.cnblogs.com/xm-blog/p/18340581

相关文章

  • Android ImageProxy 到 byteArray 并通过套接字发送
    我正在尝试将ImageProxy转换为byteArray,以通过套接字将其发送到python服务器。我正在使用Camerax,这是我的图像分析:mageAnalysisimageAnalysis=newImageAnalysis.Builder().setTargetResolution(newSize(720,640))......
  • 如何在python中使用xarray打开grib2文件?
    将xarray导入为xr导入cfgrib导入生态码将pandas导入为pddata=xr.open_dataset(r"C:\Users\new\forecast_data.grib2",engine="cfgrib")这是我的代码。我只想使用xarray读取这个文件。错误是:无法识别的引擎cfgrib必须是以下之一:['netcdf4'、'scipy'、'......
  • 2024-08-03:用go语言,给定一个从 0 开始的字符串数组 `words`, 我们定义一个名为 `isPref
    2024-08-03:用go语言,给定一个从0开始的字符串数组words,我们定义一个名为isPrefixAndSuffix的布尔函数,该函数接受两个字符串参数str1和str2。当str1同时是str2的前缀和后缀时,函数返回true;否则返回false。例如,isPrefixAndSuffix("aba","ababa")返回true,因为"ab......
  • Android开发 - (适配器)ArrayObjectAdapter类与Presenter实现类关联的作用解析
    ListRowPresenterArrayObjectAdapteradapter=newArrayObjectAdapter(newListRowPresenter());用途:用于展示ListRow中的水平滚动列表项ImageCardViewPresenterArrayObjectAdapteradapter=newArrayObjectAdapter(newImageCardViewPresenter());用途:用于显示带......
  • 龙国南方航空滑块acw_v2+cookie+风控处理+type后缀
    ​声明本文章中所有内容仅供学习交流使用,不用于其他任何目的,抓包内容、敏感网址、数据接口等均已做脱敏处理,严禁用于商业用途和非法用途,否则由此产生的一切后果均与作者无关!           本文章未经许可禁止转载,禁止任何修改后二次传播,擅自使用本文讲解的技......
  • 搞定Java ArrayList,就看这一篇!
    大家好,我是小欧!今天我们来聊聊Java中的ArrayList。作为一个Java新手,初次接触ArrayList可能会觉得有点懵,不过不用担心,这篇文章会带你从零开始一步步搞定ArrayList。我们会从基础概念开始,然后逐步深入,最后通过几个实际案例来巩固学习成果。ArrayList是什么?简单来说,ArrayLis......
  • Android开发 - (适配器)Adapter类中ArrayObjectAdapter实现类详细解析
    简介用于AndroidTV的Leanback库,用于绑定对象数组到UI组件具体作用ArrayObjectAdapter是RecyclerView和Adapter系列中用于处理列表数据的一种适配器类型,主要用于AndroidTV的Leanback库中的BrowseFragment、DetailFragment和PlaybackOverlayFragment等......
  • JAVA中实现队列和栈(Deque接口和ArrayDeque类)
    用什么来实现队列和栈首先JAVA中有一个Queue接口,用来实现队列。Deque其实就是双端队列,代表两端都可进可出的队列。ArrayDeque就是用数组来实现这个双端队列。(Deque由于是接口,只可以用于声明对象,但是没办法实例化,实例化还是要使用ArrayDeque类)这时可能就会产生疑惑,队列有了,......
  • py调用webservice array数组老是为空的问题
    pythonwebserbiceserverimportloggingfromflaskimportFlaskfromspyne.applicationimportApplicationfromspyne.protocol.soapimportSoap11fromspyne.server.wsgiimportWsgiApplicationfromwerkzeug.servingimportrun_simplefromwerkzeug.middleware......
  • LeetCode | 209 MinimumSizeSubarraySum
    分析本题中是找与target相符的最小连续的子数组和,找一个能够容纳target这么大的最小子区间。虽然本节引入了滑动窗口的概念,可我更偏好于,这是一只毛毛虫在数组上的移动,找到最小的容纳自己位置的地方target可看作毛虫本身的重量,数组中的每个元素值表示可承受的重量,right右指针看......