zcmimi's blog

arrow_back后缀数组共12篇文章

avatar
zcmimi
2020-05-13 19:00:00

简介

后缀数组,又称SA

是OI中处理字符串的有力工具

实现

有两种实现的方法

  1. 倍增法
  2. DC3

这里主要讲倍增法

sa[i]表示所有后缀中的字典序排名为i的后缀的起始位置

rnk[i]表示起始位置为i的后缀(后缀i)在所有后缀中的排名

avatar
zc
2020-05-29 17:09:00
查看原题

点击跳转

可以考虑把字符串倒序

这样添加一个字母相当于增加了一个后缀,相对原来更好处理

可以发现在插入新的字符串时,height改变的只有height[pre],height[p],height[nxt]

通过平衡树动态维护这三个位置就可以了

avatar
zc
2020-05-17 16:09:00
查看原题

点击跳转

有多种做法

AC自动机暴力

AC自动机+树状数组+lca+dfs序

后缀数组+ST表+树状数组

AC自动机暴力

原数据可以过,后来添加了加强数据就tle了

对点名串建立AC自动机,枚举名字在上面匹配,跳fail树统计

记得用于标记是否访问的数组不能用memset清零,要按原来的修改回去

玄学复杂度

avatar
zc
2020-05-16 21:36:00
查看原题

点击跳转

相同的定义为:两个子串长度相同且一个串的全部元素加上一个数就会变成另一个串

那么我们差分之后再判断即可

avatar
zc
2020-05-16 14:13:00
查看原题

点击跳转

\frac {n(n+1)}2 - \sum height[i]

avatar
zc
2020-05-16 14:13:00
查看原题

点击跳转

首先用后缀数组求出height数组

可以发现,重复出现的子串在sa数组中一定是连续的

那么在height中也是连续的

那么我们只需要求出 height数组中 连续k-1个数中 最小的数 最大可以是多少 即可

单调队列就可以解决

avatar
zc
2020-05-16 14:13:00
查看原题

点击跳转

avatar
zc
2020-05-16 14:13:00
查看原题

点击跳转

看到环就想到把原串变成两倍,而这对被延长了的原串中的子串在sa中的排名没有影响

比如baba变成babadfasdfa,这并不会影响到baba的排名

那么直接求出sa后输出即可

avatar
zc
2020-05-16 14:13:00
查看原题

点击跳转

连接所有字符串(cnt个),中间用特殊字符隔开

给每个位置标记所属字符串

然后求出sa,rnk,height数组

我们要找出cnt个所属字符串不同的后缀,让他们\operatorname{LCP}最长

可以用双指针+单调队列的方式实现

单调队列记录当前区间最小的height,单调递增,双指针移动右指针的同时维护单调队列,移动右指针后判断是否可以移动左指针,并重复到无法移动,同时对应弹出单调队列的队头

avatar
zc
2020-05-16 14:13:00
查看原题

点击跳转

1/2
Search
search