menu zcmimi's blog

arrow_back 后缀数组

可以考虑把字符串倒序

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

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

avatar
zc
2020-05-29 17:09

有多种做法

AC自动机暴力

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

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

AC自动机暴力

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

对点名串建立AC自动机

avatar
zc
2020-05-17 16:09

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

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

include<bits/stdc++.h>

define gc get

avatar
zc
2020-05-16 21:36

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

include<bits/stdc++.h>

const int N=100011; char s[N]; int

avatar
zc
2020-05-16 14:13

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

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

那么在height中也是连续的

那么我们只需要求出 height数组中 连续k-1个数中 最小的数 最大

avatar
zc
2020-05-16 14:13

```cpp

include<bits/stdc++.h>

define fur(i,x,y) for(int i=x;i<=y;++i)

const int N=1000001; char s[

avatar
zc
2020-05-16 14:13

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

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

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

avatar
zc
2020-05-16 14:13

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

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

然后求出sa,rnk,height数组

我们要找出cnt个所属字符串不同的后缀,让他们$\opera

avatar
zc
2020-05-16 14:13

```cpp

include<bits/stdc++.h>

const int N=1000111; int cnt,n,m,sa[N],rnk[N],height[N],tax[N],tp[N];

avatar
zc
2020-05-16 14:13

枚举长度L,然后判断长度为L的子串能连续出现几次(1次肯定可以,这里判断出现2次以上的)

复杂度\Theta(\frac n1+\frac n2+\cdots +\frac nn)

avatar
zc
2020-05-16 14:13
1 / 2
Search
search