后缀数组学习笔记

前言

事实上是瞎写的,给自己复习用的,不建议阅览此篇

后缀排序

两个数组(sa[N])(rk[N]),主要思想是倍增,然后用基数排序减少一个(log).
(O(n))其实没太大用。
应用:

1.模式串匹配,(sa)套个二分,复杂度(O(nlog_2n)),感觉比较鸡肋。
2.查字典序。

height

求出来上面个其实没什么很多应用,
本质是加速(height)的计算,后缀数组主要也是用(height).

引理:

[heiht[rk[i-1]]-1 leq height[rk[i]] ]

画图方便理解。
就可以(O(n))(height)
(lcp)表示两个串最长公共前缀,因为后缀是排好序的,所以很显然:

[LCP(sa[i],sa[j])=min { height[x] } (i < x leq j ) ]

就可以把很多字符串问题转化成区间上的问题,用一些数据结构维护。

套路

大概就是:
(1.)奇怪字符连接多个字符
(2.)子串就是后缀的前缀
(3.)转换成序列问题然后数据结构维护。

练习

https://oi-wiki.org/string/sa/ 的题目

原文地址:https://www.cnblogs.com/Xxhdjr/p/14875229.html