后缀数组题目选讲

后缀数组题目选讲

复习题:luogu题单

CNOI的题

\(1.\)NOI2015 品酒大会

题意:\(\forall i∈[0,n)\)求有多少对后缀满足\(lcp \ge i\)​,以及满足条件的两个后缀的权值乘积的最大值。

我们统计出对于\(1...n\)中的每个\(i\)统计一下有多少个\(lcp=i\)再做个后缀和。

因为\(lcp(i,j)=min_{i<k \le j}{heiht_k}\),我们考虑每个\(heiht_k\)能产生的贡献是一段区间。

这个是个单调栈经典问题,求出包含\(heigt_k\)且\(heigt_k\)是最大值的最长区间,然后左右长度相乘即可。

而最值可以用\(st\)表维护,维护最大和次大,最小和次小,因为最大乘积可能由两个负数相乘得出。

\(2.\)​NOI2016 优秀的拆分

计算出\(st_i\)​​​表示以\(i\)​​​​开头的\(AA\)​​​串个数,\(ed_i\)​​​表示以\(i\)​​​结尾的\(AA\)​​​串个数,我们用\(hash\)​​可以\(O(1)\)​​判断一个子串是否为\(AA\)​​串,答案就是\(\sum_{i=1}^{n-1}st_{i+1}\times ed_i\)​​,复杂度\(O(n^2)\)​​,这样就可以拿到\(95pts\)​了​​​​​​,最后5pts打表就行了

考虑如何更快的求出\(st\)​和\(ed\)​,我们枚举 \(AA\)​ 型字符串中\(A\)​的长度\(L\)。每隔\(L\)格放一个关键点,即在\(L,2L,3L...\)位置放关键点。显然,一个长度为\(2L\)的 \(AA\) 型字符串应当经过恰好两个关键点。

设\(lcp(i,j)\)​​为以\(i,j\)​后缀开头的最长公共前缀,\(lcs(i,j)\)​为以\(i,j\)​后缀结束的最长公共后缀,这个可以建正反串后缀数组求出。考虑两个相邻的关键点\(i,j\)​,其中\(i+l=j\)​ ,那么显然当\(lcp(i,j)+lcs(i,j) \ge L\)​时产生了贡献,贡献为\(lcp(i,j)+lcs(i,j)-L+1\)​​

后缀数组题目选讲

如图红色是\(i,j\)​,蓝色和绿色分别是\(lcp\)​和\(lcs\)​,其中粉色是\(AA\)​串,而这个\(AA\)​串可以一直向后滑动到棕色部分,滑动中经过的串的个数就是\(lcp(i,j)+lcs(i,j)-L+1\)​​,所以我们把红色加粗部分的所有\(st_i\)​加\(1\)​,把绿色加粗部分的所有\(ed_i\)​加\(1\)​,这个用差分实现即可。

复杂度:\(O(nlog_2n+n+\frac n 2+\frac n 3+...+1) \approx O(n \log_2 n)\)​

\(3\)​​.NOI2018 你的名字

题意: 给你一个字符串\(S\), 多次询问给定一个\(T\), 求\(T\)中不在\(S[l...r]\)​中出现的本质不同的子串个数。

老套路,把询问离线,把所有串用一个特殊字符连在一起做后缀数组。

我们按顺序枚举\(T\)​​的每个后缀\(i\)​​,我们求出最大的长度\(L\)​​使得\(\large T[i,i+L-1]\)​​是\(S[l...r]\)​​的子串,那么长度小于\(L\)​​的显然都不满足条件,可以直接计算。这个\(L\)​​是可以二分的,但是我们发现所有的\(i+L-1\)​​这个位置随着\(i\)​​的增大是单调上升的,所以双指针即可。

所以现在只要判断一个\(L\)​是否可行。事实上就是查询\(S[l...r-L+1]\)中是否存在一个\(k\)使得\(lcp(k,i) \ge L\)​,我们先求出满足这个条件的\(k\)在后缀数组上的区间\([Le,Ri]\),然后判断\([Le,Ri]\)中是否存在一个后缀\(k \in [l,r-L+1]\)​,使用主席树查询即可。

用本质不同子串个数减去上述得到的答案即可。

时间复杂度\(O(nlog_2n)\),注意常数。

\(4.\)​[HEOI2016/TJOI2016 字符串

考虑二分答案,二分一个\(L\)只需要判断是否存在一个\(k \in [b-L+1,b]\)使得\(lcp(k,c)=L\),根据上题的做法,先二分出在后缀数组的对应的区间\([Le,Ri]\)​,然后主席树查询即可。

时间复杂度\(O(nlog_2^2n)\)

CF的题

\(5.\)​CF504E

先树剖再按\(dfn\)序建立正反后缀数组,跳重链的时候记录下重链的左右端点,然后拼起来。

每次我们用\(st\)表求出\(lcp(i,j)\)​然后根据长度判断是否还能向扩展。

因为两个点之间重链个数最多只有\(2log_2n\)个,所以我们最多比较\(4log_2n\)次。

这个做法常数很小,最慢的点只要2s,目前我的账号小涵是\(luogu\)​​​的最优解

\(6\).CF666E

老套路,把所有串用一个特殊字符连在一起做后缀数组。

容易发现答案就是对于所有满足\(lcp(pl,k) \ge pr-pl+1\)​中\(col_k \in [l,r]\)​的众数。

我们考虑将询问按 \(pr-pl+1\)​ 从大到小排序,再把\(heiht_i\)​ 也从大到小排序,用两个指针,一个指向当前询问,一个指向当前的\(heiht_i\)​,我们将所有\(height_i \ge pr-pl+1\)​的进行合并操作。也就是把\(i\)​和\(i-1\)​​​​所在的集合合并,用数据结构维护众数即可,很显然用并查集+线段树合并可以很好的维护这个信息。这题的做法和noip2013 货车运输的思想是一样的,所以事实上也可以用\(kruskal\)​​重构树维护众数。

\(7.\)CF1037H

我们枚举答案与\(T\)的\(lcp\)长度\(L\),找出在后缀数组上对应的区间\([l,r]\),因为添加一个字符只会使区间缩小,所以我们用两次二分可以确定新一轮\([l,r]\)。

我们再枚第\(L+1\)​个应该填什么字符,这个字符应满足字典序是大于原字符串的对应位置的字符,按照上述同样的方法求出\([l,r]\)​,然后判断\([l,r]\)​中是否\(\exist~sa_k\in[Le,Ri-L]\)​,这个用主席树维护即可。

上一篇:crontab安装以及定时任务的执行


下一篇:了解下C# 判断