「TJOI2015」弦论

题目描述

对于一个给定长度为 \(N\) 的字符串,求它的第 \(K\) 小子串是什么。

输入格式

第一行是一个仅由小写英文字母构成的字符串 \(S\)。

第二行为两个整数 \(T\)和 \(K\),\(T\) 为 0 则表示不同位置的相同子串算作一个。\(T\) 为 1 则表示不同位置的相同子串算作多个。\(K\) 的意义如题所述。

输出格式

输出仅一行,为一个数字串,为第 \(K\) 小的子串。如果子串数目不足 \(K\) 个,则输出 -1。

样例输入

样例输出

数据范围与提示

\(N \leq 5 \times 10​ ^ 5​​, T \lt 2, K \leq 10 ^ 9 \)​​

内存限制: 256 MiB 时间限制: 1000 ms


传送门:

https://loj.ac/problem/2102http://www.lydsy.com/JudgeOnline/problem.php?id=3998


首先这道题是一个后缀自动机模板题……网上关于SAM的题解又多又好,而且这道题也是我学习SAM的动力。

不过直到学习了SAM重新审视我当时写错的SA代码,突然意识到这道题可以用SA完成,虽然常数大,但是复杂度(\(O(N)\))比SAM(\(O(N |\alpha|)\))优秀,跑得很快。

关于SAM的做法不再赘述了,我们这里考虑以SA的方式来思考这道题。

以下,\(\mathrm{sa}_i\)表示字符串\(S\)的后缀从小到大排序后开始位置,\(\mathrm{len}_i\)表示排名为\(i\)的后缀的长度(\(|S| – \mathrm{sa}_i + 1\)),\(h_i\)表示第\(i\)大后缀与第\(i – 1\)大子串的最长公共前缀(也叫\(\mathrm{LCP}\)或者\(\mathrm{height}\)),其中\(h_1 = 0\)。

当\(T = 0\)时,我们需要统计的是本质不同的字符串。显然,对于第\(i\)大的后缀,对答案的贡献只有\(\mathrm{len}_i – h_i\),因为前一个串相同的部分已经被算过答案了,然后扫一遍就好了,复杂度\(O(N)\)。

当\(T = 1\)时,我们不仅仅需要知道本质不同的字符串的个数,还需要知道依次出现了多少次以确定答案。

首先,一个非常直观的思路是,对于新出现的每个本质不同的字符串,如果长度在\([h_i, h_{i+1}]\)范围内,可以在\(h\)数组上二分 + RMQ得到出现次数;对于\(h\)数组外的部分只会出现一次,直接统计即可。

但是这样做显然是不优秀的。我们知道求\(h\)数组时我们利用了“原串相邻的两个后缀在对应位置的\(h\)的值,靠后位置的最多比靠前位置的\(h\)小\(1\)”这个结论,然而这对\(h\)数组是不适用的。这里,\(\sum_{i = 2} ^ n max(h_i – h_{i – 1}, 0)\)是可以被卡到\(O(N ^ 2)\)级别的。卡法也很简单,我们构造一个类似于abc...xyzabc...的字符串就可以把\(\sum_{i = 2} ^ n max(h_i – h_{i – 1}, 0)\)卡到\(O(N |\alpha|)\)级别,我们可以把几个字符看做一个字符,最终就能达到\(O(N ^ 2)\)的效果了。

于是看起来,\(T = 1\)时复杂度变为了\(O(\mathrm{min}(K, N ^ 2) \log N)\),显然这个复杂度是无法接受的。

那么我们就弃疗了?不。我最开始想卡这个\(O(\mathrm{min}(K, N ^ 2) \log N)\)暴力……然而发现卡不掉,就是因为我在分析时没有意识到的情况下加了一个非常简单的优化。

考虑优化。事实上我们发现,对于一个当前一个新的长度为\(\mathrm{Len}\)二分的过程结束后会得到一个值\(\mathrm{Max}\),表示出现了当前次数的字符串长度的最大值。这两个值表明,当前位置上字符串长度为\([\mathrm{Len},\mathrm{Max}]\),均出现了同样次数。那么我们将这一部分答案一并计算,最后将寻找下一个字符串从\(\mathrm{Len}++\)变为\(\mathrm{Len} = \mathrm{Max} + 1\)。

这么做,将这一步时间复杂度变为了\(O(N \log N)\);将二分替换为单调栈,这一步的时间复杂度变为\(O(N)\)。

其实,这个复杂度证明也很简单……看起来就像最大矩形面积,如果出现次数变少,一定是之后某一个位置上的高度非常小“卡住了”。因为我们求的是本质不同的字符串数量,所以对于\(h\)数组的每个元素,最多会“卡”前面的连续段一次。这样如果采用二分自然就是\(O(N \log N)\)了。发现这个性质后其实可以用单调栈,每次弹出之前的数时,用链表/vector插入出现次数到前面所弹出的位置上;因为最多弹\(O(N)\)次,所以插入的数也只有\(O(N)\)个。

由于求后缀数组也是可以\(O(N)\)的,所以总复杂度也可以是\(O(N)\)的了。这样,我们就在\(O(N)\)的时间复杂度内解决了本题;相比起后缀自动机,与字符集大小无关是这个做法更优越的一点。(由于我不会DC3我总复杂度还是只能\(O(N \log N)\) TAT但是还是跑得速度不慢啦)

二分RMQ代码如下:(这道题在BZOJ上需要交换st数组下标来卡常TAT)

单调栈代码如下:

跑得比最快的大爷慢,在LOJ上交了一发发现预处理后缀数组用了80%的时间…TAT。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

ˆ Back To Top