基本子串结构学习笔记
FutaRimeWoawaSete
·
·
个人记录
参考自《一类基础子串数据结构》
-
设字符串 \text S，\text{occ}_{\text S}(\text t) 表示字符串 \text t 在 \text S 中的出现次数。
-
设 \text {ext}(\text t) = \text T，命其为 \text t 中的扩展串。其中 \text T 包含了 \text t，表示 \text S 中最长的 \text T 满足 \text{occ}_{\text S}(\text T) = \text{occ}_{\text S}(\text t)，这是基础子串结构的核心思想。
最不济，\text{ext}(\text t) = \text t，则对于任意串存在扩展串，存在性即被说明。
对于唯一性，我们考虑若 \text{ext}(\text t) 不唯一，令取到的字符串为 \text T 和 \text T'，根据扩展串的定义，显然每一个 \text t 的位置和扩展串的位置是可以构成满射的，我们将映射建立在互相包含的位置上，由于 \text{T},\text{T'} 都包含串 \text t，所以两个相对位置的区间一定有交。
基于这种映射，我们称 \text t 的每一个出现位置和 \text{T},\text{T'} 的出现位置一一对应，即人为规定地唯一确定。
我们取 \text{T},\text{T'} 的区间并，可以得到一个长度 严格大于 |\text T|,|\text T'| 的区间子串，设为 \text{T''}。此时我们发现每个位置的 \text t 确定了至少一个 \text{T''}，并且在 |\text{T''}| 相同的情况下，每个 \text t 确定的 \text{T''} 肯定是不同位置的。可以得到 \text{occ}_{\text S}(\text {T''}) \geq \text{occ}_{\text S}(\text t)；由于 \text{T},\text{T'}\in\text{T''}，根据扩展串的定义 \text{occ}_{\text S}(\text t) = \text{occ}_{\text S}(\text T) = \text{occ}_{\text S}(\text T')\geq \text{occ}_{\text S}(\text{T''})，可以得到 \text{occ}_{\text S}(\text t) = \text{occ}_{\text S}(\text{T''})，那么存在更长的串 \text{T''} 满足扩展串的定义，矛盾。
上述的推导略繁琐，你也可以从一一对应的性质来进行更快推导。
由此，推导出扩展串存在唯一性和存在性。
-
\text{ext(ext(t))} = \text{ext}(\text t)
如果不相等，说明产生了长度更长的扩展串，那么推一下 \text{occ}_{\text S} 关系就可以反证了。
- 对于 \text t，设 \text{t'}=\text{ext(t)}，设位置 \text {t[l,r]},\text{t'[l',r']}，那么对于任意的 \text {l'}\leq \text{l''} \leq \text{l},\text {r}\leq \text{r''} \leq \text{r'}，\text{ext({s[l'',r'']})} = \text{t'}。
这个随便推一下不等式，就 \text{occ}_{\text S}(\text{t'}) \leq \text{occ}_{\text S}(\text s) \leq \text{occ}_{\text S}(\text t)，然后由 \text{occ}_{\text S}(\text{t'}) = \text{occ}_{\text S}(\text t) 就可以推出来三者的 \text{occ}_{\text S} 相同，进而推出该结论。
基本子串结构