「Learning Notes」Some Identities of Palindromic Suffix

本文会随着笔者的水平提升持续更新.
若发现文中有叙述不严谨之处,欢迎指出。

Definitions

  • 对于一个字符串 s ,定义字符串 s^{r} s 翻转后形成的字符串.
  • 对于两个字符串 s,t ,定义字符串 st 为将字符串 s t 连接起来形成的字符串.
  • 本文中的字符串均为 1-indexed.

Lemmas

Lemma 1

x,y 均为回文串且 y x 的一个后缀,则 y x 的一个 border.

Lemma 2

x,y 满足 y x 的一个长度过半的 border \left(\left|x\right|\le 2\left|y\right|\right) ,且 y 是一个回文串,则 x 也为一个回文串.

Lemma 3

x 为回文串, y x 的一个后缀,则 \left|x\right|-\left|y\right| x 的一个 period 当且仅当 y 是一个回文串.

特别地, \left|x\right|-\left|y\right| x 的最小 period 当且仅当 y x 的最长回文后缀.

Lemma 4

x 为回文串, y x 的最长回文后缀, z y 的最长回文后缀;令 u,v 满足: x=uy,y=vz 。则有:

  1. \left|u\right|\ge\left|v\right|
  2. if \left|u\right|>\left|v\right| then \left|u\right|>\left|z\right|
  3. if \left|u\right|=\left|v\right| then\ u=v

figure-1

Proof.

  1. Lemma 3 可知:若 \left|u\right|<\left|v\right| ,则 \left|u\right| 是一个比 \left|v\right| 更短的 y 的 period,这与「 y x 的最长回文后缀」相矛盾。故 \left|u\right|\ge\left|v\right|

figure-2

  1. 假设在 \left|u\right|>\left|v\right| 时存在 \left|u\right|\le\left|z\right| 的情况,记 w=zu^{r} ,则此时发现 z w 的一个长度过半的 border,由 Lemma 1 可知 w x 的一个回文后缀,而 \left|w\right|=\left|z\right|+\left|u\right|>\left|z\right|+\left|v\right|=\left|y\right| ,与「 y x 的最长回文后缀」相矛盾,故当 \left|u\right|>\left|v\right| \left|u\right|>\left|z\right|

  2. \left(2\right) 的证明中可以发现 u v 均为 x 的一个前缀,故当 \left|u\right|=\left|v\right| 时有 u=v

Lemma 5

对于一个字符串 s ,令 p 为由「 s 所有回文后缀的起始位置」组成的序列.
定义 \Delta p p 的前向差分: \Delta p_{i}=p_{i}-p_{i-1}
则有: \Delta p 单调不增,且其中的不同元素数量是 O\left(\log{|S|}\right) 的。
亦即: 一个字符串 s 的所有回文后缀的长度可以形成 O\left(\log{|S|}\right) 个等差数列.

Proof.

Lemma 4 (1) 容易知道 \Delta p 单调不增.
又由 Lemma 4 \left(2\right) 可知当 \Delta p 下降即 \left|u\right|>\left|v\right| 时,有 \left|x\right|>\left|u\right|+\left|z\right|>2\left|z\right| ,即每次 \Delta p 的下降都会引发当前后缀长度减半,故 \Delta p 中最多有 O\left(\log{|S|}\right) 个不同的值。

Identities

References

A Subquadratic Algorithm for Minimum Palindromic Factorization