BZOJ 1396 识别子串 题解

Statement

给 \(S\)，令 \(x\) 为 \(S\) 的第 \(k\) 个字符，称 \(T=S[i..j]\) 为关于 \(x\) 的识别子串，当且仅当：

• \(i\le k\le j\)（含 \(x\) 这一位）
• \(T\) 在 \(S\) 中只出现一次

求 \(S\) 关于每一位字符的最短识别子串长度，\(|S|\le 10^5\).

Solution 1

以下是我没看题解瞎胡的

首先一个非常弱智的想法是，建 SAM，\(T\) 相当于 \(\text{endpos}\) 集合大小为 1，再维护个出现位置，全拎出来，用两个线段树区间取 \(\min\)，注意这里单 log 因为可以标记永久化。

但是这是 SA 练习题所以要用 SA 做一遍。

怎么做呢，后面忘了

Solution 2

以下是我看别的做法，转述的

SA 做法：对于每个后缀 \(i\)，都可以求出从 \(i\) 向后延伸的最短识别子串，为 \(\max(\text{height}(\text{rk}(i)),\text{height}(\text{rk}(i)+1))+1\)，注意 \(i\) 可能没有向后延伸的识别子串。

于是正一遍，反一遍，线段树区间取 \(\min\) 即可。