题目大意:
给定一个长为 \(n\) 的字符串 \(S\),你要找到最大的 \(k\),使得存在 \(s_{1} \sim s_{k}\) 使得 \(s_{1}\) 是 \(S\) 子串 且 \(s_{i}\) 在 \(s_{i - 1}\) 中作为子串至少出现两次。
\(n \le 2 \times 10^5\)。
解题思路:
考虑至少出现两次的条件是不好做的,但是我们贪心地倒推 \(s_{i}\) 与 \(s_{i - 1}\) 的关系,由于 \(s_{i - 1}\) 越小越好,所以最后一定会让 \(s_{i}\) 变成 \(s_{i - 1}\) 的 border。
但是我们发现沿着这条路是不好走的,因为要求 \(s\) 内每一个字串最多跳多少次 border。
对于字符串的题,我们可以套路地设 \(dp_{i}\) 表示以 \(i\) 为后缀的答案,要求 \(s_{1}\) 以 \(i\) 开头。
因为我们发现对于 border 是不断缩小的,而且无后效性。
那么为了转移,我们肯定要再设一个 \(len_{i}\) 表示 \(k\) 最大的情况下 \(s_{1}\) 最小是多少。
但是考虑直接转移是不对的,因为 \(dp\) 值大但可能转移不到后面,而且我们必须设一个状态数线性的 dp,不然会直接爆掉。
我们尝试一下能不能修锅。
考虑先把 \(dp\) 值算出来,因为每个 \(dp\) 能更新的在 SA 上是一段区间,所以能 \(O(n \log n)\)。
现在的问题是对于两个位置 \(j,k\),\(j\) 的 \(len_{j}\) 不能直接更新 \(len_{i}\),但 \(len_{k}\) 可以,而我们又要求的是最小的,所以希望取 \(len_{j}\) 的前缀。
由于 \(k \sim k + len_{k} - 1\) 是以 \(i\) 为开头的后缀的前缀,所以 \(i \sim i + len_{i} - 1\) 等于 \(k \sim k + len_{k} - 1\)。
也就是我们只需要找到 \(LCP(i,j) >= len_{k}\) 的最前面的位置就行了。
而 \(len_{k}\) 就找到最小的即可。
O(n \log n)。