临界分解定理及其应用
Leasier
·
·
算法·理论
临界分解定理及其应用
可能需要的前置知识：词理论基础。
8.1 预备知识
定义 8.1.1 (周期)
设 w \in A^+，令 n = |w| \in \mathbb{N}_+，记 p = \pi(w) 为使 w 成为长度为 p 的词的某个幂的子词的 最小 正整数，称为 w 的 周期 (period)；称满足条件的词为 w 的循环根。
进一步地，称 w 本原 若其不是其一个循环根的真幂（这与 定义 1.3.1 是一致的），称 w 主要 (primary) 若其为自身的循环根，称其 w 有周期性 (periodic) 若 n \geq 2p。
记 w 的循环根的集合为 \sqrt{w}。
例子 8.1.2
- (1) 取 w = aaabaa，有 \pi(w) = 4，其循环根为 aaab, aaba, abaa, baaa；其是本原的；其不是主要或有周期性的；其循环根都是本原的，但其中只有 aaab, baaa 是主要的。
- (2) 取 w = aaabaaabaa，有 \pi(w) = 4，其循环根与上面一致；其是本原的；其不是主要的；其是有周期性的。
命题 8.1.3 (周期的等价定义)
设 w = a_1 \cdots a_n \in A^+ \ (a_i \in A)，则下列三个命题等价：
(1) p = \pi(w)。\
(2) p = n - |v|，其中 v 为 w 的最长真边界。\
(3) p 为最小的正整数使得 \forall 1 \leq i \leq n - p, a_i = a_{i + p}。
Proof. 记命题 i 给出的 p 为 p_i，显见 1 \leq p_i \leq n。
$(2) \Leftrightarrow (3)$：由 $v$ 的定义可见 $\forall 1 \leq i \leq |v|, a_i = a_{i + p_2}$，故而由 $p_3$ 的最小性可知 $p_3 \leq p_2$；同时可见 $a_1 \cdots a_{n - p_3} \neq w$ 同时为 $w$ 的前缀和后缀，故而由 $|v|$ 的最大性可知 $|v| \geq n - p_3$，也即 $p_2 \leq p_3$。总之 $p_2 = p_3$，明所欲证。
------
称 $w = a_1 \cdots a_n \in A^+ \ (a_i \in A)$ 有 **弱周期 (weak period)** $1 \leq p \leq n$，若 $\forall 1 \leq i \leq n - p, a_i = a_{i + p}$。则该命题指出周期无非是最小的弱周期。
#### 命题 8.1.4 (周期的单调性)
> 设 $w \in A^+$，若 $w'$ 为 $w$ 的非空子词，则 $\pi(w') \leq \pi(w)$。
_Proof._ 若 $w$ 为 $z^t$ 的子词则 $w'$ 亦然，由最小性即得 $\pi(w') \leq \pi(w)$。
#### 命题 8.1.5 (循环根的基本性质)
> 设 $w = a_1 \cdots a_n \in A^+ \ (a_i \in A)$，$p = \pi(w)$，令 $P = a_1 \cdots a_p$，则 $\sqrt{w}$ 恰为 $P$ 的共轭类，且其中全为本原字。
_Proof._ 由 **命题 8.1.3 (3)** 可知 $P \in \sqrt{w}$ 且 $w$ 为 $P^{\lceil \frac{n}{p} \rceil}$ 的子词，由 $p$ 的最小性可知 $P$ 本原，故 $P$ 的共轭类中全为本原字。
任取 $P$ 的共轭类中的 $P_i = a_i \cdots a_p a_1 \cdots a_{i - 1}$，则 $w$ 为 $P_i^{\lceil \frac{n}{p} \rceil + 1}$ 的子词，故 $P_i \in \sqrt{w}$；同时，任取 $u = b_1 \cdots b_p \in \sqrt{w}$，设 $w$ 为 $u^t$ 的子词，则 $\exists 1 \leq i_0 \leq pt - n + 1, \text{s.t. } \forall 1 \leq j \leq n, a_j = (u^t)[i_0 + j - 1] = b_{(i_0 + j - 2) \bmod p + 1}$，令 $r = (i_0 - 1) \bmod p + 1$，则 $a_1 = b_r, \cdots, a_{p - r + 1} = b_p; a_{p - r + 2} = b_1, \cdots, a_p = b_{r - 1} (r > 1)$，即 $u = a_{p - r + 2} \cdots a_p a_1 \cdots a_{p - r + 1} = P_{(p - r + 1) \bmod p + 1}$，故 $u$ 属于 $P$ 的共轭类。
总之 $\sqrt{w}$ 恰为 $P$ 的共轭类，且其中全为本原字，明所欲证。
#### 定理 8.1.6 (Fine & Wilf, 周期表述)
> 设 $w_1, w_2 \in A^*, u \in A^+$，令 $w = w_1 uw_2$，$p_1 = \pi(w_1 u), p_2 = \pi(uw_2), d = \gcd(p_1, p_2)$，若 $|u| \geq p_1 + p_2 - d$，则 $p_1 = p_2 = \pi(w)$。
_Proof._ 令 $v_1' = (w_1 u)_{1 \sim p_1}, v_2 = (uw_2)_{1 \sim p_2}$，$v_1$ 为 $v_1'$ 向右循环移位 $|w_1|$ 所得的字（_即与 $u$ 开头重合_），则 $v_1, v_2$ 的某一对幂有长度为 $|u| \geq p_1 + p_2 - d$ 的公共前缀，由 **定理 1.3.8** 可知 $v_1, v_2$ 为同一个字 $s$ 的幂。
**命题 8.1.5** 指出 $v_1, v_2$ 本原，则 $v_1 = v_2 = s, p_1 = p_2 = |s|$。由 **命题 8.1.3 (3)** 可知 $\pi(w) \leq |s|$，但同时据 **命题 8.1.4** 有 $|s| = p_1 = p_2 = \pi(w_1 u) = \pi(uw_2) \leq \pi(w)$，故而 $p_1 = p_2 = \pi(w)$。
### 8.2 临界分解定理
#### 定义 8.2.1 (真分解, 交叉因子, 虚周期, 临界分解)
设 $w = a_1 \cdots a_n \in A^+ \ (a_i \in A)$，在 $1 \leq i < n$ 处将其切分为 $w_1 = a_1 \cdots a_i, w_2 = a_{i + 1} \cdots a_n$，称 $(w_1, w_2)$ 为 $w$ 的真分解。
称 $u$ 为 $(w_1, w_2)$ 的 **交叉因子 (cross factor)**，若 $u$ 与 $w_1$ 在后缀关系下可比（即 $u$ 为 $w_1$ 的后缀，或 $w_1$ 为 $u$ 的后缀），且 $u$ 与 $w_2$ 在前缀关系下可比（即 $u$ 为 $w_2$ 的前缀，或 $w_2$ 为 $u$ 的前缀）。记 $(w_1, w_2)$ 的所有交叉因子构成集合：
$$
C(w_1, w_2) = \{u \in A^+ \mid A^* u \cap A^* w_1 \neq \varnothing \land u A^* \cap w_2 A^* \neq \varnothing\}
$$
> _Rmk._ 交叉因子显然存在：$u = w_2 w_1$ 即为一例。
称 $(w_1, w_2)$ 的所有交叉因子中最短者的长度为 $(w_1, w_2)$ 的 **虚周期 (virtual period)**，记作 $p(w_1, w_2)$。
称 $(w_1, w_2)$ 为 $w$ 的 **临界分解 (critical factorization)**，若 $p(w_1, w_2) = \pi(w)$。
#### 命题 8.2.2 (虚周期 $\leq$ 周期)
> 设 $(w_1, w_2)$ 为 $w \in A^+$ 的真分解，则 $p(w_1, w_2) \leq \pi(w)$。
_Proof._ 令 $p = \pi(w)$。当 $|w_1| \geq p$，则循环根 $u = a_{i - p + 1} \cdots a_i$ 为 $w_1$ 的后缀，称之 **左内 (left internal)**。此时若 $|w_2| \geq p$，则 $u$ 也为 $w_2$ 的前缀；若 $|w_2| < p$，则 $w_2$ 为 $u$ 的前缀，并称之 **右外部 (right external)** ——总之必有 $u \in C(w_1, w_2)$。
当 $|w_1| < p$，同样可以发现总有一个循环根在 $C(w_1, w_2)$ 中。总之由虚周期的最小性可知 $p(w_1, w_2) \leq p$，明所欲证。
#### 例子 8.2.3
设 $w = a^n b^m \ (n, m \in \mathbb{N}_+)$，除 $(a^n, b^m)$ 外其每个真分解的虚周期都是 $1$，唯独这一个是 $n + m = \pi(w)$。
#### 定理 8.2.4 (临界分解定理)
> 设 $p = \pi(w) > 1$，$0 \le j \le |w| - p$，则 $w$ 的任一长度为 $p - 1$ 的相继真分解构成的集合 $\{(w_{i, 1}, w_{i, 2}) \mid j < |w_{i, 1}| < j + p\}$ 都包含至少一个临界分解，相应的最短交叉因子正是 $w$ 的一个主要循环根。
在开始证明之前，首先留意到下面的推论。
#### 推论 8.2.5
> 设 $w \in A^+$ 本原，则 $w$ 的共轭类中包含主要字。
_Proof._ 当 $|w| = 1$ 显然；当 $|w| = \pi(w) > 1$，由 **定理 8.2.4** 可知 $w$ 的所有相继真分解中包含临界分解，相应的最短交叉因子是 $w$ 的一个主要循环根，也即处在 $w$ 的共轭类中。
#### 例子 8.2.6 (临界分解定理的界是紧的)
设 $w = a^n ba^n \ (n \in \mathbb{N}_+)$，有 $p = \pi(w) = n + 1$ 且其恰有两个临界分解 $(a^n, ba^n), (a^n b, a^n)$，这意味着集合中至少需要包含 $n = p - 1$ 项。
------
下面开始 **定理 8.2.4** 的证明。
_Proof._ 考虑对 $|w| > 1$ 归纳。当 $|w| = 2$，无非是分情况讨论 $w = a^2, w = ab \ (a, b \in A, a \neq b)$ 两种情况，验证是容易的。
> **命题 8.2.7**
> > 任一临界分解 $(w_1, w_2)$ 的任一最短交叉因子 $u$ 都是主要的。
>
> _Proof._ 假设 $u$ 不是主要的，由 **命题 8.1.3** 可知这无非是说 $\exists v, p_1, p_2 \in A^+, \text{s.t. } u = vp_1 = p_2 v$。\
> 由 $A^* u \subset A^* v, A^* u \cap A^* w_1 \neq \varnothing$ 可知 $A^* v \cap A^* w_1 \neq \varnothing$，由 $uA^* \subset vA^*, uA^* \cap w_2 A^* \neq \varnothing$ 可知 $vA^* \cap w_2 A^* \neq \varnothing$。总之 $v \in C(w_1, w_2)$，但 $|v| < |u|$，故 $u$ 不是最短的交叉因子，矛盾！
> **命题 8.2.8**
> > 任一临界分解 $(w_1, w_2)$ 的最短交叉因子 $u$ 唯一。
>
> _Proof._ 假设 $u'$ 也是 $(w_1, w_2)$ 的最短交叉因子，则 $u, u'$ 的后 $\min(|u|, |w_1|)$ 位和前 $\min(|u|, |w_2|)$ 位分别相同，只需证明 $\min(|u|, |w_1|) + \min(|u|, |w_2|) \geq |u|$。\
> 若 $|u| \leq \max(|w_1|, |w_2|)$ 不等式显然成立；否则只需证明 $|u| \leq |w_1| + |w_2|$，而 $u = w_2 w_1$ 确为 $(w_1, w_2)$ 的交叉因子，由 $u$ 的最短性可知不等式成立。
> **引理 8.2.9**
> > 考虑相继真分解 $(w_1, w_2)$，设 $y \in A^+$ 为 $w_1$ 的非空后缀或 $w_2$ 的非空前缀，令 $q = \pi(y)$，设 $u$ 为 $(w_1, w_2)$ 的最短交叉因子，则 $|u| \leq q$ 或 $|u| > |y|$。
>
> _Intuition._ 最短交叉因子要么 **“很短”**、被困在周期内，要么 **“很长”**、超出了词本身的长度。\
> _Proof._ 考虑反证法：假设 $q < |u| \leq |y|$，只需证明 $u$ 不是 $(w_1, w_2)$ 的最短交叉因子；由 **命题 8.2.7** 可知只需证明这样的 $u$ 不是主要的。\
> 只需证明 $y$ 为 $w_1$ 的后缀的情况，另一情形的证明同理：此时 $u$ 为 $y$ 的非空后缀。\
> 由 $q = \pi(y)$ 可知存在 $|z| = q$ 给出 $y$ 为 $z^t$ 的后缀，进而 $u$ 也为 $z^t$ 的后缀，故 $\pi(u) \leq q < |u|$，由 **命题 8.1.3** 可知 $u$ 不是主要的。
> **命题 8.2.10**
> > 设 $(w_1, w_2)$ 为 $w$ 的临界分解，$b \in A$，则：
> > > (1) 若 $\pi(w) = \pi(wb)$，则 $(w_1, w_2 b)$ 为 $wb$ 的临界分解。\
> > > (2) 若 $\pi(w) < \pi(wb)$，则 $(w_1, w_2 b)$ 为 $wb$ 的临界分解当且仅当 $(w_1, w_2)$ 为右外部，此时 $(w_1, w_2 b)$ 为双边外部。
> >
> > 也有考察 $(bw_1, w_2)$ 为 $bw$ 的临界分解的对称情况，不再赘述。
>
> _Intuition._ 这是归纳法中“向后添加一个字符”的 **步进器**。\
> _Proof._ 设 $u, v$ 分别为 $(w_1, w_2), (w_1, w_2 b)$ 的最短交叉因子，则 $\pi(w) = |u| \leq |v|$ 且等号成立当且仅当 $u = v$；由 **命题 8.2.2** 可知 $|v| \leq \pi(wb)$。
> > (1) 若 $\pi(w) = \pi(wb)$，有 $|v| \leq \pi(wb) = \pi(w) = |u|$，则 $|v| = |u| = \pi(wb)$，故 $(w_1, w_2 b)$ 也为 $wb$ 的临界分解。\
> > (2) 若 $\pi(w) \neq \pi(wb)$，由 **命题 8.1.4** 可知有 $|u| = \pi(w) < \pi(wb)$。欲证 $|v| = \pi(wb)$ 当且仅当 $|u| > |w_2|$，且此时还有 $|v| > |w_1|, |v| > |w_2 b|$。\
> > 先证必要性：此时有 $|u| < |v|$。
> > > (i) 假设 $|u| \leq |w_2|$，则 $u$ 也为 $(w_1, w_2 b)$ 的交叉因子，由最短性可知 $|v| \leq |u|$，矛盾！\
> > > (ii) 假设 $|v| \leq |w_1|$，由 **引理 8.2.9** 可知必有 $|v| \leq \pi(w_1)$，再由 **命题 8.1.4** 可知 $\pi(w_1) \leq \pi(w)$，总之有 $|v| \leq \pi(w) = |u|$，矛盾！\
> > > (iii) 假设 $|v| \leq |w_2 b|$，则 $|u| < |v| \leq |w_2| + 1 \Rightarrow |u| \leq |w_2|$，由 (i) 推出矛盾！
> >
> > 再证充分性：此时有 $|u| > |w_2|$。
> > > (i) 假设 $|v| \leq |w_1|$，则同上面 (ii) 推出 $u = v$，由 $|u| > |w_2|$ 可知 $|u| \geq |w_2 b|$，然后分 $w_1, w_2 b$ 两部分考察可以推知 $u$ 的某个幂包含 $wb$，由最小性可知 $\pi(wb) \leq |u| = \pi(w)$，矛盾！\
> > > (ii) 假设 $|v| \leq |w_2 b|$，则同上面 (iii) 推出 $|u| \leq |w_2|$，矛盾！
> >
> > 总之 $wb$ 必为 $v^2$ 的子词，由最短性可知 $\pi(wb) \leq |v|$，故 $|v| = \pi(wb)$。
> **命题 8.2.11**
> > 设 $w = a_1 \cdots a_n \ (n > 1, a_i \in A)$，记 $w = w_1 w_2 \ (w_1, w_2 \neq \varnothing)$，若 $w$ 有弱周期 $1 \leq p \leq |w_2|$，则 $\forall b \in A$，下列命题等价：
> > > (1) $wb$ 有弱周期 $p$。\
> > > (2) $w_2 b$ 有弱周期 $p$。\
> > > (3) $b = a_{n - p + 1}$。
>
> _Proof._ 已知 $\forall 1 \leq i \leq n - p, a_i = a_{i + p}$，则 (1) 即 $\forall 1 \leq i \leq n - p, a_i = a_{i + p} \land b = a_{n - p + 1}$，(2) 即 $\forall |w_1| + 1 \leq i \leq n - p, a_i = a_{i + p} \land b = a_{n - p + 1}$。三者的等价性是显见的。
> **推论 8.2.12**
> > 设 $w = a_1 \cdots a_n \ (n > 1, a_i \in A)$，$b \in A$，记 $w = a_1 w'$，若 $\pi(w' b) \leq \pi(w)$，则 $w$ 的每个临界分解 $(w_1, w_2)$ 都诱导出 $wb$ 的一个临界分解 $(w_1, w_2 b)$。\
> > 也有考察 $(bw_1, w_2)$ 为 $bw$ 的临界分解的对称情况，不再赘述。
>
> _Intuition._ “首尾交错”诱导临界分解的条件。\
> _Proof._ 若 $\pi(w) = \pi(wb)$，由 **命题 8.2.10 (1)** 可见命题成立。下面讨论 $\pi(w) < \pi(wb)$ 的情况，由 **命题 8.2.10 (2)** 可知这无非是证明 $(w_1, w_2)$ 为右外部。\
> 设 $u$ 为 $(w_1, w_2)$ 的最短交叉因子，则 $\pi(w) = |u|$。假设其不为右外部即 $|u| \leq |w_2|$，则由交叉条件可见 $u$ 为 $w_2$ 的前缀、进而为 $w' b$ 的子词。\
> 由 **命题 8.2.7** 可知 $\pi(u) = |u|$，又由 **命题 8.1.4** 和假设、条件可知 $|u| = \pi(u) \leq \pi(w' b) \leq \pi(w) = |u|$，故 $\pi(w' b) = |u|$。\
> 显见 $|u| < n$，故由 **命题 8.2.11** 可知 $wb$ 有周期 $|u|$，则 $\pi(wb) \leq |u| = \pi(w)$，与 $\pi(w) < \pi(wb)$ 矛盾。明所欲证。
下面讨论 $n = |w| > 2$ 的情况。设 $w = a_1 \cdots a_n \ (a_i \in A)$，记 $w = w' a_n = a_1 w''$，$p = \pi(w), q = \pi(w'), r = \pi(w'')$，对 $p, q, r$ 的关系分类讨论：
> (i) 若 $q = p$，对 $0 \leq j \leq n - p$ 分类讨论：
> > I. 当 $j < n - p$，据归纳假设从 $w'$ 的相继真分解集 $\{(w'_{i, 1}, w'_{i, 2}) \mid j < |w'_{i, 1}| < j + p\}$ 中取出临界分解 $(w'_1, w'_2)$，由 **命题 8.2.10 (1)** 可见，$(w'_1, w'_2 a_n)$ 也构成 $w$ 的临界分解，此即 $w$ 的相继真分解集 $\{(w_{i, 1}, w_{i, 2}) \mid j < |w_{i, 1}| < j + p\}$ 中的临界分解。\
> > II. 当 $j = n - p$，若 $r = p$ 则通过与 I 完全对称的情况可得。下面讨论 $r < p$ 的情况。\
> > 由于 $p > 1$ 和 $p = q \leq |w'| = n - 1$，只需证明 $w'$ 的满足 $|w'_1| = n - p$ 的相继真分解 $(w'_1, w'_2)$ 不是临界分解，随后可见上述 $j = n - p - 1$ 给出的临界分解仍合法。\
> > 考虑 $w = a_1 \cdot w'' \cdot \varnothing$，由于 $r < p$，据 **定理 8.1.6** 可见 $n - 1 = |w''| < p + r - \gcd(p, r) \leq 2p - 2 \Rightarrow 1 \leq |w'_1| = n - p \leq p - 2$。\
> > 假设这个 $(w'_1, w'_2)$ 是临界分解，设 $v$ 为相应的最短交叉因子，则由 **命题 8.2.7** 可知 $\pi(v) = |v| = p$。\
> > 由 $|w'_2| = p - 1$ 可知 $v = w'_2 b \ (b \in A)$，而 $w'_1$ 一侧则给出 $b = a_{n - p}$；另一方面，$w$ 的周期指出 $a_n = a_{n - p}$，故 $v = w'_2 a_n$ 为 $w''$ 的后缀，因此 $p = \pi(v) \leq \pi(w'') = r < p$，矛盾！
>
> (ii) 若 $r = p$，这一情形与 (i) 完全对称。\
> (iii) 若 $q, r < p$，对 $q$ 分类讨论：
> > I. 当 $q = 1$，可见 $w'$ 形如 $b^{n - 1} \ (b \in A, b \neq a_n)$，由 **命题 8.1.3** 可知 $p = n$，同时有临界分解 $(b^{n - 1}, a_n)$，命题成立。\
> > II. 当 $q > 1$，对 $r$ 分类讨论：
> > > [i] 若 $r \leq q$，$\forall 0 \leq j \leq n - p < n - q$，据归纳假设从 $w'$ 的相继真分解集 $\{(w'_{i, 1}, w'_{i, 2}) \mid j < |w'_{i, 1}| < j + q\}$ 中取出临界分解 $(w'_1, w'_2)$，由 **推论 8.2.12** 和 $r \leq q$ 可知 $(w'_1, w'_2 a_n)$ 为所求的临界分解。\
> > > [ii] 若 $q < r \leq p$，$\forall 1 \leq j \leq n - p < n - q$，同样据归纳假设从 $w''$ 的相继真分解集 $\{(w''_{i, 1}, w''_{i, 2}) \mid j - 1 < |w''_{i, 1}| < j + r - 1\}$ 中取出临界分解 $(w''_1, w''_2)$，由 **推论 8.2.12 对称情况** 和 $q < r$ 可知 $(a_1 w''_1, w''_2)$ 为所求的临界分解。\
> > > 特别地，对于 $j = 0$ 的情况，由 $r < p$ 可见上述 $j = 1$ 给出的临界分解仍合法。
总之我们构造性地完成了归纳步进，明所欲证。
#### 推论 8.2.13
> 设 $w \in A^+ \ (|w| > 1)$，则 $w$ 至少包含一个临界分解。
_Proof._ 当 $\pi(w) = 1$，$w$ 形如 $a^n \ (a \in A)$，则任一相继真分解都构成临界分解；当 $\pi(w) > 1$，在临界分解定理中任取 $j$ 即得。
------
接下来的两个命题将指出，当切分点从左到右变化时，虚周期如何随交叉因子的位置类型变化，并由它们导出 **推论 8.2.16** 的单峰性质。
#### 命题 8.2.14
> 设 $w_1, w_2 \in A^+, x \in A^*$，$u, v$ 为 $(w_1, xw_2), (w_1 x, w_2)$ 的最短交叉因子。\
> (1) 若 $u$ 为左内右外部，则 $v$ 为左内部，且有 $|u| \geq |v|$，等式成立当且仅当 $v$ 为右外部且与 $u$ 共轭。\
> (2) 若 $v$ 为左外右内部，则 $u$ 为右内部，且有 $|v| \geq |u|$，等式成立当且仅当 $u$ 为左外且与 $v$ 共轭。
_Proof._ (2) 与 (1) 完全对称，下面只证明 (1)；由于 $x = \varepsilon$ 时两个分解相同、命题平凡地成立，下设 $x \in A^+$。
由 $u$ 为左内右外部可知 $w_1 = zu, u = xw_2 y \ (y, z \in A^*)$，则 $(w_1 x, w_2) = (zxw_2 yx, w_2)$，故 $w_2 yx$ 为其交叉因子，由最短性可知 $|v| \leq |w_2 yx| = |u| < |w_1 x|$，则 $v$ 为左内。
当等式成立，由 **命题 8.2.8** 可知 $v = w_2 yx$，则 $|v| \geq |w_2| + |y| + |x| > |w_2|$，故 $v$ 为右外部且与 $u$ 共轭。
#### 命题 8.2.15
> 设 $(w_1, w_2)$ 为 $w \in A^+$ 的相继真分解，$u$ 为其最短交叉因子，若 $u$ 为左外右外部，则其为临界分解。
_Proof._ 由 $u$ 为左外右外部可知 $u = y_1 w_1 = w_2 y_2 \ (y_1, y_2 \in A^+)$，由 $|y_1| + |w_1| = |w_2| + |y_2| = |u| \leq \pi(w) \leq |w| = |w_1| + |w_2|$ 可知 $|y_1| \leq |w_2|, |y_2| \leq |w_1|$，设 $w_2 = y_1 v$，则 $w_1 = vy_2, u = y_1 vy_2$。
设 $v_l$ 为最长的同时为 $w_1$ 的前缀和 $w_2$ 的后缀的词，由 $v_l$ 的最长性可知 $|v| \leq |v_l|$；另一方面 $v_l$ 诱导出 $w_1 = v_l y_{l, 2}, w_2 = y_{l, 1} v_l$ 和交叉因子 $u_l = y_{l, 1} v_l y_{l, 2}$，由 $u$ 的最短性可知 $|w| - |v| = |u| \leq |u_l| = |w| - |v_l| \Rightarrow |v_l| \leq |v|$。总之有 $|v_l| = |v| \Rightarrow v_l = v$。
由 **命题 8.1.3** 可知 $\pi(w) = |w| - |v_b|$，其中 $v_b$ 为 $w$ 的边界，则由其最长性可知 $|v| \leq |v_b|$；另一方面由 **命题 8.2.2** 可知 $|w| - |v| = |u| \leq \pi(w) = |w| - |v_b|$ 即 $|v_b| \leq |v|$。总之有 $|v_b| = |v| \Rightarrow v_b = v$。
综上 故 $\pi(w) = |w| - |v_b| = |w| - |v| = |u|$，即 $(w_1, w_2)$ 为临界分解。
#### 推论 8.2.16 (虚周期的单峰性)
> 设 $J$ 为 $w \in A^+$ 的非双边内部的相继真分解构成的集合，按切分点从左到右排列，则 $J$ 中的分解按左外右内部、左外右外部、左内右外部的顺序出现（允许类型缺席）。\
> 进一步地，对应的虚周期序列 $(p_j)_{j \in J}$ 单峰，即不存在 $j < j' < j''$ 使得 $p_j > p_{j'} < p_{j''}$，且峰值 $\leq \pi(w)$。
_Proof._ 当 $\pi(w) = 1$，所有相继真分解都是左内右内部，命题平凡地成立；下面讨论 $\pi(w) > 1$ 的情形。
对 $J$ 中任意两个切分点 $j < j'$，令 $w_1 = a_1 \cdots a_j, w_2 = a_{j' + 1} \cdots a_n, x = a_{j + 1} \cdots a_{j'} \in A^*$，则 $w$ 的两个相继真分解为 $(w_1, xw_2), (w_1 x, w_2)$。由 **命题 8.2.14 (1)** 可知：若 $j$ 处为左内右外部，则 $j'$ 处为左内部；而 $J$ 中左内部的类型只有左内右外部，故 $j'$ 处亦为左内右外部，且 $p_j \geq p_{j'}$。
同理由 **命题 8.2.14 (2)** 可知：若 $j'$ 处为左外右内部，则 $j$ 处为右内部；而 $J$ 中右内部的类型只有左外右内部，故 $j$ 处亦为左外右内部，且 $p_{j'} \geq p_j$。
于是左内右外部一旦出现，其后（在 $J$ 中）全为左内右外部；左外右内部一旦出现，其前（在 $J$ 中）全为左外右内部。故 $J$ 中的分解按左外右内部、左外右外部、左内右外部的顺序出现（允许类型缺席），其中虚周期在左外右内部段单调不减、左内右外部段单调不增，而左外右外部段则由 **命题 8.2.15** 可见为临界分解，其虚周期恰为 $\pi(w)$。
总之由 **命题 8.2.2** 可见各 $p_j \leq \pi(w)$，故 $(p_j)_{j \in J}$ 单峰且峰值 $\leq \pi(w)$，且当左外右外段存在时可以取得。明所欲证。
> _Rmk._ 左外右外部的相继真分解可能不存在，如 $w = aba$。
### 8.3 度的有界性
#### 定义 8.3.1 ($X$-解释, 不交, $X$-度, 覆盖)
设 $w = a_1 \cdots a_n \ (a_i \in A)$，$\varnothing \neq X \subset A^+$ 为有限集，且 $\forall x \in X, |x| < n$。
$w$ 的一个 **$X$-解释 ($X$-interpretation)** 指一个形如 $w = x_0 \cdots x_{r + 1}$ 的分解，其中 $\forall 1 \leq i \leq r, x_i \in X$，$x_0$ 为 $X$ 中某词的真后缀，且 $x_{r + 1}$ 为 $X$ 中某词的真前缀。
称 $w$ 的两个解释 $w = x_0 \cdots x_{r + 1} = y_0 \cdots y_{s + 1}$ **无交 (disjoint)**，若 $\forall 0 \leq i \leq r, 0 \leq j \leq s, x_0 \cdots x_i \neq y_0 \cdots y_j$。
$w$ 的 **$X$-度 ($X$-degree)** 指最多能选出的两两不交的 $X$-解释的数量。
设 $v = a_i \cdots a_j \ (1 \leq i \leq j \leq n)$ 为 $w$ 的子词，取 $x \in X$ 满足 $|x| \geq j - i + 1$，$x$ 对 $v$ 的 **覆盖 (covering)** 指 $w$ 的子词 $x' = a_{i'} \cdots a_{j'} \ (1 \leq i' \leq i \leq j \leq j' \leq n)$，使得以下三者之一成立：(i) $x' = x$；(ii) $i' = 1$ 且 $x'$ 为 $x$ 的真后缀；(iii) $j' = n$ 且 $x'$ 为 $x$ 的真前缀。
#### 定理 8.3.2
> 若 $w \in A^+$ 的周期大于 $X$ 中所有词的周期，则 $w$ 的 $X$-度最多为 $|X|$。
在开始证明之前，首先说明定理的界是“比较紧”的——可以构造 $X$-度为 $|X| - 1$ 的情形。
#### 例子 8.3.3
取 $A = \{a, b\}$，$X$ 为前缀码 $\{a^p\} \sqcup \{a^i ba^{q(i)} \mid i \in \{0, \cdots, p - 1\}\}$，其中 $q$ 为 $0 \sim p - 1$ 的一个排列。
当 $w \in (a^* a^{2p - 2} b)^* a^* a^{2p - 2}$，容易验证 $w$ 的 $X$-度恰为 $p = |X| - 1$。
------
下面开始 **定理 8.3.2** 的证明。
_Proof._ 先证下面这个引理：
> **引理 8.3.4**
> > 设 $w = a_1 \cdots a_n = w_1 v w_2 \ (a_i \in A)$，其中 $v = a_i \cdots a_j \ (1 \leq i \leq j \leq n)$，若有两个 $x$ 对 $v$ 的覆盖 $x'_1, x'_2$，则当 $v_1 v_2 = v$，有 $p(w_1 v_1, v_2 w_2) \leq p = \pi(x)$。
>
> _Proof._ 设 $x'_1 = a_{i_1} \cdots a_{j_1}, x'_2 = a_{i_2} \cdots a_{j_2}$，不妨设 $i_1 \leq i_2, j_1 \leq j_2$，其中至少有一个不等号是严格的，分类讨论：
> > (i) 若 $x'_1 = x'_2 = x$，则 $d \triangleq i_2 - i_1 = j_2 - j_1 \in (0, |x|]$，于是 $\forall i_1 \leq k < k + d \leq j_2, a_k = a_{k + d}$，则 $(w_1 v_1, v_2 w_2)$ 有长为 $d$ 的交叉因子，设 $q = p(w_1 v_1, v_2 w_2)$，则 $q \leq d$。\
> > 若 $q > p = \pi(x) \geq \pi(a_{i_1} \cdots a_{i - 1} v_1)$，则由 **引理 8.2.9** 可知 $q > |a_{i_1} \cdots a_{i - 1} v_1| \geq i - i_1 \geq i_2 - i_1 = d$，矛盾！故 $q \leq p$，明所欲证。\
> > (ii) 若 $x'_1$ 为 $x$ 的真后缀但 $x'_2$ 不然，设 $x = y_1 x'_1$，考虑 $w_1 \mapsto y_1 w_1$，易见 $C(w_1 v_1, v_2 w_2) \supset C(y_1 w_1 v_1, v_2 w_2)$ 进而有 $p(w_1 v_1, v_2 w_2) \leq p(y_1 w_1 v_1, v_2 w_2)$。\
> > 再看若 $x'_2$ 为 $x$ 的真前缀但 $x'_1$ 不然，类似地改变 $w_2$ 不会增加虚周期。随后转化为 (i) 的情况。\
> > (iii) 若 $x'_1, x'_2$ 同为 $x$ 的真后缀或真前缀，不妨设为前者，则有 $i_1 = i_2 = 1, j_1 < j_2$，且 $x'_1$ 为 $x'_2$ 的真后缀，由 **命题 8.1.4** 可知 $\pi(x'_2) \leq \pi(x)$，考虑 $x \mapsto x'_2$，随后转化为 (ii) 的情况。
>
> 综上我们穷尽了所有情况，明所欲证。
设 $w = a_1 \cdots a_n \ (a_i \in A)$，显见 $n > 1$，则由 **推论 8.2.13** 取 $w$ 的一个临界分解 $(w_1, w_2)$，则 $l = |w_1| < n$。
对于每一个 $X$-解释 $w = x_0 \cdots x_{r + 1}$，存在最小的 $s$，使得 $|x_0 x_1 \cdots x_s| \geq l$，则 $x_s$ 是 $X$ 中某个词对 $a_l$ 的覆盖。
若存在多于 $|X|$ 个两两不交的 $X$-解释，则其中至少两个对应的 $x_s$ 相同，由 **引理 8.3.4** 可知 $p(w_1, w_2) \leq \pi(x_s) < \pi(w)$，与 $(w_1, w_2)$ 的临界性矛盾！旋即得证。
### 8.4 Two-Way 算法 (Crochemore & Perrin, 1991)
这是临界分解定理在 **模式匹配** 问题中的一个经典应用，glibc 的字符串搜索实现包含 Two-Way 算法：当前 `strstr` 对很长的模式串采用的是 Two-Way 算法（核心实现在 [`string/str-two-way.h`](https://github.com/bminor/glibc/blob/master/string/str-two-way.h)）。
> _Rmk._ 下面统一采取从 $1$ 开始的下标。\
> _Rmk._ 若 $\pi(x) = 1$，则 $x$ 退化为 $a^n \ (a \in A)$，模式匹配问题退化为连续重复字符的匹配，扫一遍即可；下面的算法皆是针对 $\pi(x) > 1$ 的情形。
#### 算法 8.4.1 (Two-Way 算法, (小周期) 匹配部分)
> 输入：词 $x, t \in A^+$、$p = \pi(x) > 1$ 和临界位置 $l < p$（其存在性由 **定理 8.2.4** 保证）。\
> 输出：$P(x, t) = \{1 \leq q \leq |t| - |x| + 1 \mid x = t[q, q + |x| - 1]\}$。\
> 大致流程：记 $x = x_1 x_2 \ (|x_1| = l)$。从左到右扫描，尝试将 $x_2$ 与 $t$ 匹配：
> > (i) 若失配，则右移模式串使得临界位置处在导致失配的字母的右侧。\
> > (ii) 若匹配完全，则从右到左扫描 $x_1$ 与 $t$ 匹配，此时若匹配完全则加入输出集合；接着将模式串右移 $p$ 位，并记忆已经匹配的模式串的前缀长度。
>
> 伪代码：
> $$
> \begin{array}{l}
> \textbf{function} \ \text{Positions}(x, t): \\
> \qquad (\text{给定}: p := \pi(x); \ l \ \text{为满足} \ l < p \ \text{的临界位置};) \\
> \qquad \text{pos} := 1; \ s := 0; \ P := \varnothing; \\
> \qquad \textbf{while} \ \text{pos} + |x| - 1 \leq |t| \ \textbf{do} \\
> \qquad \qquad i := \max(l, s) + 1; \\
> \qquad \qquad \textbf{while} \ i \leq |x| \land x[i] = t[\text{pos} + i - 1] \ \textbf{do} \ i := i + 1; \\
> \qquad \qquad \textbf{if} \ i \leq |x| \ \textbf{then} \\
> \qquad \qquad \qquad \text{pos} := \text{pos} + (i - l); \\
> \qquad \qquad \qquad s := 0; \\
> \qquad \qquad \textbf{else} \\
> \qquad \qquad \qquad j := l; \\
> \qquad \qquad \qquad \textbf{while} \ j > s \land x[j] = t[\text{pos} + j - 1] \ \textbf{do} \ j := j - 1; \\
> \qquad \qquad \qquad \textbf{if} \ j \leq s \ \textbf{then} \ P := P \cup \{\text{pos}\}; \\
> \qquad \qquad \qquad \text{pos} := \text{pos} + p; \\
> \qquad \qquad \qquad s := |x| - p; \\
> \qquad \qquad \textbf{end if} \\
> \qquad \textbf{end while} \\
> \qquad \textbf{return} \ P; \\
> \textbf{end function}
> \end{array}
> $$
假若我们已经取得了 $p, l$，下面证明算法的性质。
#### 引理 8.4.2
> 设 $x \in A^+$ 有临界分解 $(x_1, x_2)$，若其有长为 $r \leq \max(|x_1|, |x_2|)$ 的交叉因子，则 $\pi(x) \mid r$。
_Proof._ 不妨设 $r \leq |x_2|$，$r \leq l$ 的情形是完全对称的。
记 $p = \pi(x)$，令 $r' = r \mod p$，则 $x_2[1, r'] = x_2[r - r' + 1, r]$。若 $r' > 0$，则 $(x_1, x_2)$ 有长为 $r'$ 的交叉因子，与临界分解的性质矛盾！故 $r' = 0$，即 $r$ 为 $p(x)$ 的倍数。
#### 命题 8.4.3 (算法 8.4.1 的正确性)
> 函数 $\text{Positions}$ 正确计算 $P(x, t)$。
_Proof._ 设 $P'$ 为算法输出的集合 `P`，欲证：
- (i) 若 $q \in P'$，则 $x = t[q, q + |x| - 1]$。
- (ii) 若 $x = t[q, q + |x| - 1]$，则 $q \in P'$。
首先断言外层循环维护不变式：
$$
x[i] = t[\text{pos} + i - 1], \quad \forall 1 \leq i \leq s
$$
验证则是容易的：初始及失配时执行 $s \leftarrow 0$ 平凡成立；匹配完全时执行 $s \leftarrow |x| - p$，这是因为在 $\text{pos}$ 赋值之前有 $\forall l < i \leq |x|, x[i] = t[\text{pos} + i - 1]$，由 $l < p$ 可见在其赋值之后有 $\forall 1 \leq i \leq |x| - p = s, x[i] = x[i + p] = t[\text{pos} + i - 1]$。
> (i) 若 $q \in P'$，则当 $\text{pos} = q$，$i$ 的循环确保 $\forall \max(l, s) < i \leq |x|, x[i] = t[q + i - 1]$，$j$ 的循环确保 $\forall s < j \leq l, x[j] = t[q + j - 1]$，再配合循环不变式即得 $x = t[q, q + |x| - 1]$。\
> (ii) 若 $x = t[q, q + |x| - 1]$，设某轮外层循环中将 $\text{pos}$ 从 $q_1$ 改为 $q_2$。$q_1 = q$ 时同 (i) 可见 $q \in P'$。\
> 下面讨论 $q_1 < q < q_2$ 的情形。设 $i$ 的循环结束后 `i` 的值为 $i'$，这轮循环开头 `s` 的值为 $s$，分类讨论：
> > I. 若 $i' > |x|$，则 $x_2$ 出现在 $t[q_1 + l]$ 处，由 $x = t[q, q + |x| - 1]$ 可知 $x_2 = t[q_1 + l, q_1 + |x| - 1] = t[q + l, q + |x| - 1]$，这意味着 $(x_1, x_2)$ 有长为 $q - q_1$ 的交叉因子，则 $q - q_1 \geq p = q_2 - q_1 \Rightarrow q \geq q_2$，矛盾！\
> > II. 若 $\max(l, s) < i' \leq |x|$，则 $x[l + 1, i' - 1] = t[q_1 + l, q_1 + i' - 2]$ 但 $x[i'] \neq t[q_1 + i' - 1]$。\
> > 若 $q < q_1 + i' - l$，可见 $(x_1, x_2)$ 有长为 $q - q_1 \leq i' - l \leq |x| - l$ 的交叉因子，由 **引理 8.4.2** 可知 $p \mid q - q_1$，故 $x[i'] = x[i' - q + q_1] = t[q + i' - q + q_1 - 1] = t[q_1 + i' - 1]$，矛盾！故 $q \geq q_1 + i' - l = q_2$，矛盾！
#### 命题 8.4.4 (算法 8.4.1 的比较次数)
> 函数 $\text{Positions}$ 的字母比较次数不超过 $2|t|$。
_Proof._ 将字母比较分为 $x[i] = t[\text{pos} + i - 1]$ 和 $x[j] = t[\text{pos} + j - 1]$ 两类计算：
> (i) 对于前者，断言每次字母比较使得 $\text{pos} + i$ 增加：
> > I. 若 $i < |x|$ 且字母匹配，则 $i$ 增加 $1$、$\text{pos}$ 不变，命题成立。\
> > II. 若 $i = |x|$ 且字母匹配，则 $i$ 增加 $1$，接下来会将 $\text{pos}$ 增加 $p$、将 $s$ 置为 $|x| - p$，下一轮会将 $i$ 重置为 $\max(l, s) + 1$，只需说明 $\text{pos} + |x| < (\text{pos} + p) + (\max(l, s) + 1)$，而这是显然的。\
> > III. 若字母不匹配，则 $i$ 不变、$\text{pos}$ 增加 $i - l > 0$，下一轮会将 $i$ 重置为 $l + 1$，只需说明 $\text{pos} + i < (\text{pos} + (i - l)) + (l + 1)$，而这同样是显然的。
>
> (ii) 对于后者，留意到每次比较读到的 $\text{pos} + j - 1$ 两两不同：因为每次 $j$ 的循环结束后 $\text{pos}$ 会增加 $p$，但 $l < p$。
总之两者对应的比较次数各自不超过 $|t|$，故总次数不超过 $2|t|$。
#### 推论 8.4.5 (算法 8.4.1 的复杂度)
> 在 RAM 模型下，$\text{Positions}$ 的时间复杂度为 $O(|t|)$，除 $x, t, p, l, P$ 外的额外空间复杂度为 $O(1)$。
_Proof._ 时间复杂度由 **命题 8.4.4** 立即可得；而额外空间复杂度仅由 $\text{pos}, s, i, j$ 带来，总量 $O(1)$。
------
现在我们还需解决 $p, l$ 的计算。一篇较近的论文 [3] 给出了一个不依赖字典序的、时空复杂度皆为 $O(|x|)$ 但较为复杂的算法；这里我们假定存在全序 $(A, \leq)$，它按照 **定义 5.1.1** 诱导出 $A^*$ 上的字典序 $(A^*, \leq)$；并介绍一个时间复杂度为 $O(|x|)$、额外空间复杂度为 $O(1)$ 的算法。
> _Rmk._ 笔者初看时感觉有些匪夷所思：为什么“序”在匹配问题中能够发挥作用？一个粗略的理解可能是周期与字典序之间的确存在某种关联。\
> ~~集合论中的良序原理在某种程度上或许也是如此：“序”的确是一种非常基础的“结构”，能够给很多“操作”提供条件。~~
由 **命题 8.1.3** 可知我们可以通过 KMP 算法的 `fail` 数组计算 $p$，但这样将会引入 $O(|x|)$ 的额外空间复杂度；但事实上我们 **不总是** 需要使用精确的周期值。
同时，序关系的引入会给出一种更简洁的计算 $l$ 的方式，其威力正是通过 **引理 8.4.6** 和 **引理 8.4.8** 加以展现。
#### 引理 8.4.6
> 设有全序 $(A, \leq)$，反转得到全序 $(A, \subseteq)$，若 $x \leq y, x \subseteq y$，则 $x$ 为 $y$ 的前缀。
_Proof._ 对 $|x|$ 归纳即得。
#### 定理 8.4.7
> 设有全序 $(A, \leq)$，反转得到全序 $(A, \subseteq)$。设 $x \in A^+ \ (p = \pi(x) > 1)$，令 $v, v'$ 分别为 $x$ 在 $\leq, \subseteq$ 意义下的最大后缀，令 $x = uv = u' v'$。\
> (1) 若 $|v| \leq |v'|$，则 $(u, v)$ 为临界分解，否则 $(u', v')$ 为 $x$ 的一个临界分解。\
> (2) $|u|, |u'| < p = \pi(x)$。
_Proof._ 不妨设 $|v| \leq |v'|$，另一情形是完全对称的。
(1) 首先证明 $u \neq \varepsilon$：若不然有 $x = v = v'$，设 $x = ax' \ (a \in A)$，则有 $x' \leq x, x' \subseteq x$，由 **引理 8.4.6** 可知 $x'$ 为 $x$ 的前缀，因此 $x$ 的边界长为 $|x| - 1$，由 **命题 8.1.3** 可知 $p = 1$，矛盾！
下面的引理指出 $(u, v)$ 的最短交叉因子不可能为左内右内部。
> **引理 8.4.8**
> > 设 $v$ 为 $x \in A^+$ 的最大后缀，令 $x = uv$，则 $(u, v)$ 没有左内右内部的非空交叉因子。
>
> _Proof._ 设 $w \in A^+$ 同时为 $u$ 的后缀和 $v$ 的前缀，令 $v = wt$，由 $v$ 的最大性可知 $wv \leq v, t \leq v$，前者即 $w^2 t \leq wt \Leftrightarrow wt \leq t$，后者即 $t \leq wt$。因此 $wt = t$，故 $w = \varepsilon$。
故而令 $r = p(u, v)$，则 $r \leq |u|, r \leq |v|$ 不同时成立。若 $r \leq |u|$，则 $r > |v|$，可见 $v$ 为 $u$ 的子词，而从 $v$ 在 $u$ 中的位点出发延伸到 $x$ 的结尾所得的词严格大于 $v$，与 $v$ 的最大性矛盾！故 $r > |u|$。
因而设 $yu \ (y \in A^+, |yu| = r)$ 为 $(u, v)$ 的最短交叉因子，对 $r, |v|$ 的关系分类讨论：
> (i) 若 $r > |v|$，由 **命题 8.2.2** 可知 $r \leq p$，但同时由于 $x$ 是 $(uy)^2$ 的前缀，有 $p \leq |uy| = r$。总之 $p = r = p(u, v)$，即 $(u, v)$ 为临界分解。\
> (ii) 若 $r \leq |v|$，同 (i) 理可见只需证明 $x$ 有弱周期为 $r$。\
> 设 $u = u' z, v = yus$，由 $v$ 的最大性可知 $s \leq v$，由 $v'$ 的最大性可知 $zs \subseteq v' = zv \Leftrightarrow s \subseteq v$，由 **引理 8.4.6** 可知 $s$ 为 $v$ 的前缀。\
> 归纳可见 $x = uyus$ 为 $(uy)^t us \ (t \in \mathbb{N}_+)$ 的前缀，取 $t$ 使得 $t|uy| \geq |x|$ 即得 $x$ 为 $(uy)^t$ 的前缀，故 $x$ 有弱周期 $|uy| = r$，明所欲证。
(2) 由 (1) 可知 $|u| < r = p$，而由 $|v| \leq |v'|$ 可知 $|u'| \leq |u|$，故有 $|u'| \leq |u| < p$。
------
至此 $l$ 的计算完全转化为最大后缀的计算；事实上 **定理 8.4.7** 也给出了临界分解定理的一个较弱形式的构造性证明。下面的内容大致分为三部分：
- A. 在 $O(|x|)$ 时间、$O(1)$ 额外空间内计算最大后缀。
- B. 基于 A，在 $O(|x|)$ 时间、$O(1)$ 额外空间内精确计算小周期 / 估计大周期的下界。
- C. 综合 AB 及 **算法 8.4.1**，在 $O(|x| + |t|)$ 时间、$O(1)$ 额外空间内求解 $P(x, t)$。
#### 定义 8.4.9 (最大后缀及其周期)
设有全序 $(A, \leq)$，对 $x \in A^+$ 令 $\max(x)$ 表示其最大后缀，设 $\max(x) = u^e v$，其中 $|u| = \pi(\max(x))$ 而 $v$ 为 $u$ 的真前缀，令 $\text{per}(x) = u, \text{rest}(x) = v$。
#### 引理 8.4.10
> 设 $x \in A^+$，取 $a \in A$ 使得 $\text{rest}(x) a$ 为 $\max(x)$ 的前缀，若 $\max(x)$ 有真边界 $w$，且 $|w| > |\text{rest}(x)|$，则 $wa$ 为 $\max(x)$ 的前缀。
_Proof._ 设 $u = \text{per}(x), v = \text{rest}(x), \max(x) = u^e v$，则 $u = vav'$。对 $w$ 分类讨论：
> (i) 若 $w$ 为 $\max(x)$ 的最长真边界，则由 **命题 8.1.3** 足见 $w = u^{e - 1} v$，故 $\max(x) = wav' v$，即 $wa$ 为 $\max(x)$ 的前缀。\
> (ii) 若 $w$ 不为 $\max(x)$ 的最长真边界，则 $w$ 为 $u^{e - 1} v$ 的真后缀，由 (i) 可见 $\max(x) = u^{e - 1} vav' v$，因而 $wav' v$ 为 $\max(x)$ 的真后缀。\
> 设 $\max(x) = wbs$，则由最大性可知 $wav' v \leq \max(x) = wbs \Rightarrow a \leq b$。\
> 由 $|w| > |v|$ 及 $w, v$ 均为 $\max(x)$ 的边界可知 $v$ 为 $w$ 的真后缀，因此 $vbv' v$ 为 $\max(x)$ 的真后缀，则由最大性可知 $vbv' v \leq \max(x) = vav' u^{e - 1} v \Rightarrow b \leq a$。\
> 综上有 $a = b$，故 $wa$ 为 $\max(x)$ 的前缀。
#### 命题 8.4.11
> 设 $x \in A^+, a \in A$，取 $a' \in A$ 使得 $\text{rest}(x) a'$ 为 $\max(x)$ 的前缀，则有：
> $$
> \begin{aligned}
> \max(xa) &= \begin{cases}
> \max(x) a, &\quad a \leq a' \\
> \max(\text{rest}(x) a), &\quad a > a'
> \end{cases} \\
> \text{per}(xa) &= \begin{cases}
> \max(x) a, &\quad a < a' \\
> \text{per}(x), &\quad a = a' \\
> \text{per}(\text{rest}(x) a), &\quad a > a'
> \end{cases} \\
> \text{rest}(xa) &= \begin{cases}
> \varepsilon, &\quad a < a' \lor (a = a' \land \text{rest}(x) a = \text{per}(x)) \\
> \text{rest}(x) a, &\quad a = a' \land \text{rest}(x) a < \text{per}(x) \\
> \text{rest}(\text{rest}(x) a), &\quad a > a'
> \end{cases}
> \end{aligned}
> $$
> _Rmk._ 可以发现有种 Lyndon 分解的感觉；事实上两者的思想确有相似之处。
_Proof._ 对 $a, a'$ 的关系分类讨论：
> (i) 当 $a < a'$，下证 $\max(x) a$ 没有非空真边界：
> > I. $a \neq a'$ 意味着不存在长为 $1$ 的边界。\
> > II. 假设 $wa \ (w \neq \varepsilon)$ 为 $\max(x) a$ 的真边界，则 $w$ 为 $\max(x)$ 的边界，对 $w$ 的长度分类讨论：
> > > [i] 若 $|w| < |\text{rest}(x)|$，则 $w$ 为 $\text{rest}(x)$ 的非空真边界，设 $\text{rest}(x) = wb w' \ (b \in A)$，则 $wb$ 为 $\max(x)$ 的前缀，同时 $wa'$ 为 $\max(x)$ 的子词，因而最大性指出 $wa' \leq wb \Leftrightarrow a' \leq b$，进而 $a < b$，因此 $wa$ 不为 $\max(x)$ 的前缀。\
> > > [ii] 若 $|w| \geq |\text{rest}(x)|$，由 $a \neq a'$ 立即可得 $wa$ 不为 $\max(x)$ 的前缀。
>
> 因此 $\pi(\max(x) a) = |\max(x) a|$。
> 另一方面，易见只需证明 $\max(x) a$ 在其后缀中最大：设 $w$ 为 $\max(x)$ 的真后缀，则有 $\max(x) > w$，同时上面的讨论指出 $w$ 不可能为 $\max(x)$ 的前缀，故 $\max(x) a > wa$。因此有：
> $$
> \max(xa) = \max(x) a, \quad \text{per}(xa) = \max(x) a, \quad \text{rest}(xa) = \varepsilon
> $$
> (ii) 当 $a = a'$，显见 $\max(xa) = \max(x) a$，同时 $\pi(\max(xa)) \geq \pi(\max(x))$ 但 $\text{per}(x)$ 仍为 $\max(xa)$ 的弱周期，故 $\text{per}(xa) = \text{per}(x)$，因此有：
> $$
> \text{rest}(xa) = \begin{cases}
> \varepsilon, &\quad \text{rest}(x) a = \text{per}(x) \\
> \text{rest}(x) a, &\quad \text{otherwise}
> \end{cases}
> $$
> (iii) 当 $a > a'$，令 $wa = \max(xa)$，则 $w$ 为 $\max(x)$ 的后缀，故 $w \leq \max(x)$。若 $w$ 不为 $\max(x)$ 的前缀，则 $w < \max(x)$，于是 $wa < \max(x) a$，然而最大性指出 $\max(x) a \leq \max(xa) = wa$，矛盾！\
> 故 $w$ 为 $\max(x)$ 的前缀。若 $|w| > |\text{rest}(x)|$ 则由 **引理 8.4.10** 可知 $wa$ 为 $\max(x)$ 的前缀，与 $a \neq a'$ 矛盾！故 $|w| \leq |\text{rest}(x)|$，因此有：
> $$
> \max(xa) = \max(\text{rest}(x) a), \quad \text{per}(xa) = \text{per}(\text{rest}(x) a), \quad \text{rest}(xa) = \text{rest}(\text{rest}(x) a)
> $$
#### 算法 8.4.12 (Two-Way 算法, 最大后缀的计算)
> 输入：词 $x \in A^+$ 和全序 $(A, \leq)$。\
> 输出：$(i, r)$，其中 $i$ 为 $\max(x)$ 之前部分的长度，$r$ 为 $\max(x)$ 的周期。\
> 伪代码：
> $$
> \begin{array}{l}
> \textbf{function} \ \text{Maximal-Suffix}(x): \\
> \qquad i := 0; \ j := 1; \ k := 1; \ r := 1; \\
> \qquad \textbf{while} \ j + k \leq |x| \ \textbf{do} \\
> \qquad \qquad a := x[j + k]; \ a' := x[i + k]; \\
> \qquad \qquad \textbf{if} \ a < a' \ \textbf{then} \\
> \qquad \qquad \qquad j := j + k; \ k := 1; \ r := j - i; \\
> \qquad \qquad \textbf{else if} \ a = a' \ \textbf{then} \\
> \qquad \qquad \qquad \textbf{if} \ k = r \ \textbf{then} \ j := j + r; \ k := 1; \\
> \qquad \qquad \qquad \textbf{else} \ k := k + 1; \\
> \qquad \qquad \textbf{else} \\
> \qquad \qquad \qquad i := j; \ j := j + 1; \ k := 1; \ r := 1; \\
> \qquad \qquad \textbf{end if} \\
> \qquad \textbf{end while} \\
> \qquad \textbf{return} \ (i, r); \\
> \textbf{end function}
> \end{array}
> $$
> _Rmk._ 伪代码中 $j$ 记录 $\max(x)$ 中最后一个周期结束的位置，$k$ 记录 $|\text{rest}(x)| + 1$。
#### 命题 8.4.13 (算法 8.4.12 的正确性)
> 函数 $\text{Maximal-Suffix}$ 正确计算 $(i, r)$。
_Proof._ 算法维护循环不变式：
$$
\begin{aligned}
& \max(x[1, j + k - 1]) = x[i + 1, j + k - 1] \\
\land\ & |\text{per}(x[1, j + k - 1])| = r \\
\land\ & |\text{rest}(x[1, j + k - 1])| = k - 1 \\
\land\ & i + k \leq j
\end{aligned}
$$
对 $a, a'$ 的关系分类讨论，随后正确性据 **命题 8.4.11** 实属显然。
#### 命题 8.4.14 (算法 8.4.12 的比较次数)
> 函数 $\text{Maximal-Suffix}$ 的字母比较次数不超过 $2|x| - 1$。
_Proof._ 断言每次字母比较使得 $i + j + k$ 增加：
> (i) 若 $a < a'$，则 $i + j + k$ 增加 $1$。\
> (ii) 若 $a = a'$，则 $i + j + k$ 增加 $1$。\
> (iii) 若 $a > a'$，则 $i + j + k$ 变为 $2j + 2$，由循环不变式可知这至少是 $i + j + k + 2$，因此 $i + j + k$ 至少增加 $2$。
在循环过程中，有 $0 \leq i \leq |x|, 2 \leq j + k \leq |x| + 1$，故 $2 \leq i + j + k \leq 2|x| + 1$，其有 $2|x|$ 个不同取值，故比较次数不超过 $2|x| - 1$。
#### 定理 8.4.15 (算法 8.4.12 的复杂度)
> 在 RAM 模型下，$\text{Maximal-Suffix}$ 的时间复杂度为 $O(|x|)$，除 $x, i, r$ 外的额外空间复杂度为 $O(1)$。
_Proof._ 时间复杂度由 **命题 8.4.14** 立即可得；而额外空间复杂度仅由 $j, k$ 带来，总量 $O(1)$。
#### 命题 8.4.16
> 设 $x \in A^+$ 有临界分解 $(u, v)$，其中 $|u| < \pi(x)$。设 $v = y^e z \ (e \in \mathbb{N}_+)$，其中 $|y| = \pi(v)$ 且 $z$ 为 $y$ 的真前缀。\
> 若 $|u| < \dfrac{|x|}{2}$ 且 $u$ 为 $y$ 的后缀则 $\pi(x) = \pi(v)$，否则 $\pi(x) > \max(|u|, |v|)$。
_Proof._ 分类讨论：
> (i) 若 $|u| < \dfrac{|x|}{2}$ 且 $u$ 为 $y$ 的后缀，则 $x$ 为 $y^{e + 2}$ 的子词，故 $x$ 有弱周期为 $\pi(v)$，这意味着 $\pi(x) \leq \pi(v)$，但 **命题 8.1.4** 指出 $\pi(v) \leq \pi(x)$，故 $\pi(x) = \pi(v)$。\
> (ii) 若 $|u| < \dfrac{|x|}{2}$ 但 $u$ 不为 $y$ 的后缀，欲证 $\pi(x) > \max(|u|, |v|) = |v|$。\
> 假设 $\pi(x) \leq |v|$，由 **引理 8.2.9** 可知 $\pi(x) \leq \pi(v)$，同 (i) 可见 $\pi(x) = \pi(v)$，因此 $y$ 就是 $(u, v)$ 的交叉因子，但由 $|y| = \pi(x) > |u|$ 可见 $u$ 为 $y$ 的后缀，矛盾！\
> (iii) 若 $|u| \geq \dfrac{|x|}{2}$，由条件立即可得 $\pi(x) > |u| = \max(|u|, |v|)$。
#### 算法 8.4.17 (Two-Way 算法, 周期的计算与估计)
> 输入：词 $x \in A^+$，全序 $(A, \leq)$。\
> 输出：$r$，满足若 $l < \dfrac{|x|}{2}$ 且 $x[1, l]$ 为 $x[l + 1, l + r]$ 的后缀则 $r = \pi(x)$，否则 $r \leq \pi(x)$。\
> 伪代码：
> $$
> \begin{array}{l}
> \textbf{function} \ \text{Small-Period}(x): \\
> \qquad (l_1, r_1) := \text{Maximal-Suffix}(x, \leq) \\
> \qquad (l_2, r_2) := \text{Maximal-Suffix}(x, \subseteq) \\
> \qquad \textbf{if} \ l_1 \geq l_2 \ \textbf{then} \\
> \qquad \qquad l := l_1; \ r := r_1; \\
> \qquad \textbf{else} \\
> \qquad \qquad l := l_2; \ r := r_2; \\
> \qquad \textbf{end if} \\
> \qquad \textbf{if} \ l < \dfrac{|x|}{2} \land x[1, l] \ \text{为} \ x[l + 1, l + r] \ \text{的后缀} \ \textbf{then} \\
> \qquad \qquad \textbf{return} \ r; \\
> \qquad \textbf{else} \\
> \qquad \qquad \textbf{return} \ (\max(l, |x| - l) + 1); \\
> \qquad \textbf{end if} \\
> \textbf{end function}
> \end{array}
> $$
#### 命题 8.4.18 (算法 8.4.17 的正确性)
> 函数 $\text{Small-Period}$ 在 $l < \dfrac{|x|}{2}$ 且 $x[1, l]$ 为 $x[l + 1, l + r]$ 的后缀时返回 $r = \pi(x)$，否则返回 $\max(l, |x| - l) + 1 \leq \pi(x)$。
_Proof._ 当 $\pi(x) = 1$ 时容易验证命题成立；下面讨论 $\pi(x) > 1$ 的情况。
记 $(u, v)$ 为 **定理 8.4.7** 给出的临界分解即 $l = |u| < \pi(x)$，则 $r = \pi(v)$ 且 $x[l + 1, l + r]$ 为 $v = y^e z$ 的周期段 $y$。
> (i) 若 $l < \dfrac{|x|}{2}$ 且 $x[1, l]$ 为 $x[l + 1, l + r]$ 的后缀，由 **命题 8.4.16** 可知返回 $r = \pi(v) = \pi(x)$。\
> (ii) 若 $l \geq \dfrac{|x|}{2}$ 或 $x[1, l]$ 不为 $x[l + 1, l + r]$ 的后缀，由 **命题 8.4.16** 可知返回 $r = \max(l, |x| - l) + 1 \leq \pi(x)$。
总之返回值 $r$ 满足要求，明所欲证。
> _Rmk._ 当 $\pi(x) \leq \dfrac{|x|}{2}$，有 $l < \pi(x) \leq \dfrac{|x|}{2}$，若 $x[1, l]$ 不为 $x[l + 1, l + r]$ 的后缀则由 **命题 8.4.16** 可见 $\pi(x) > \max(l, |x| - l) \geq \dfrac{|x|}{2}$，矛盾！\
> 故 $x[1, l]$ 为 $x[l + 1, l + r]$ 的后缀，则由 **命题 8.4.18** 可见此时返回周期的精确值。这正是函数 $\text{Small-Period}$ 得名的缘由。
#### 算法 8.4.19 (Two-Way 算法, (大周期) 匹配部分)
> 输入：词 $x, t \in A^+ \ (\pi(x) > 1)$、$1 \leq r \leq \pi(x)$ 和临界位置 $l < \pi(x)$（其存在性由 **定理 8.2.4** 保证）。\
> 输出：$P(x, t) = \{1 \leq q \leq |t| - |x| + 1 \mid x = t[q, q + |x| - 1]\}$。\
> 伪代码：
> $$
> \begin{array}{l}
> \textbf{function} \ \text{Positions-Large-Period}(x, t): \\
> \qquad (\text{给定}: 1 \leq r \leq \pi(x); \ l \ \text{为满足} \ l < \pi(x) \ \text{的临界位置};) \\
> \qquad \text{pos} := 1; \ P := \varnothing; \\
> \qquad \textbf{while} \ \text{pos} + |x| - 1 \leq |t| \ \textbf{do} \\
> \qquad \qquad i := l + 1; \\
> \qquad \qquad \textbf{while} \ i \leq |x| \land x[i] = t[\text{pos} + i - 1] \ \textbf{do} \ i := i + 1; \\
> \qquad \qquad \textbf{if} \ i \leq |x| \ \textbf{then} \\
> \qquad \qquad \qquad \text{pos} := \text{pos} + (i - l); \\
> \qquad \qquad \textbf{else} \\
> \qquad \qquad \qquad j := l; \\
> \qquad \qquad \qquad \textbf{while} \ j > 0 \land x[j] = t[\text{pos} + j - 1] \ \textbf{do} \ j := j - 1; \\
> \qquad \qquad \qquad \textbf{if} \ j \leq 0 \ \textbf{then} \ P := P \cup \{\text{pos}\}; \\
> \qquad \qquad \qquad \text{pos} := \text{pos} + r; \\
> \qquad \qquad \textbf{end if} \\
> \qquad \textbf{end while} \\
> \qquad \textbf{return} \ P; \\
> \textbf{end function}
> \end{array}
> $$
#### 命题 8.4.20 (算法 8.4.19 的正确性)
> 函数 $\text{Positions-Large-Period}$ 正确计算 $P(x, t)$。
_Proof._ 依 **命题 8.4.3** 之葫芦画瓢即可，不再赘述。
#### 命题 8.4.21 (算法 8.4.19 的比较次数)
> 当 $\max(l, |x| - l) < r \leq \pi(x)$，函数 $\text{Positions-Large-Period}$ 的字母比较次数不超过 $2|t|$。
_Proof._ 仍将字母比较分为 $x[i] = t[\text{pos} + i - 1]$ 和 $x[j] = t[\text{pos} + j - 1]$ 两类计算：
> (i) 对于前者，断言每次字母比较使得 $\text{pos} + i$ 增加：
> > I. 若 $i < |x|$ 且字母匹配，与 **命题 8.4.4** 的证明一致。\
> > II. 若 $i = |x|$ 且字母匹配，则 $i$ 增加 $1$，接下来会将 $\text{pos}$ 增加 $r$，下一轮会将 $i$ 重置为 $l + 1$，只需说明 $\text{pos} + |x| < (\text{pos} + r) + (l + 1)$，而这依旧是显然的。\
> > III. 若字母不匹配，与 **命题 8.4.4** 的证明一致。
>
> (ii) 对于后者，留意到每次比较读到的 $\text{pos} + j - 1$ 依旧两两不同：因为每次 $j$ 的循环结束后 $\text{pos}$ 会增加 $r$，但 $l < r$。
总之两者对应的比较次数各自依旧不超过 $|t|$，故总次数不超过 $2|t|$。
#### 推论 8.4.22 (算法 8.4.19 的复杂度)
> 在 RAM 模型下，$\text{Positions-Large-Period}$ 的时间复杂度为 $O(|t|)$，除 $x, t, r, l, P$ 外的额外空间复杂度为 $O(1)$。
_Proof._ 时间复杂度由 **命题 8.4.21** 立即可得；而额外空间复杂度仅由 $\text{pos}, i, j$ 带来，总量 $O(1)$。
------
最终，结合 **算法 8.4.1**、**算法 8.4.12**、**算法 8.4.17**、**算法 8.4.19**，我们给出完整的算法。
#### 算法 8.4.23 (Two-Way 算法, 完整版)
> 输入：词 $x, t \in A^+ \ (\pi(x) > 1)$，全序 $(A, \leq)$。\
> 输出：$P(x, t) = \{1 \leq q \leq |t| - |x| + 1 \mid x = t[q, q + |x| - 1]\}$。\
> 在 RAM 模型下，时间复杂度：$O(|x| + |t|)$；除 $x, t, P$ 外的额外空间复杂度：$O(1)$。\
> 伪代码：
> $$
> \begin{array}{l}
> \textbf{function} \ \text{Match}(x, t): \\
> \qquad (l_1, r_1) := \text{Maximal-Suffix}(x, \leq); \\
> \qquad (l_2, r_2) := \text{Maximal-Suffix}(x, \subseteq); \\
> \qquad \textbf{if} \ l_1 \geq l_2 \ \textbf{then} \\
> \qquad \qquad l := l_1; \ r := r_1; \\
> \qquad \textbf{else} \\
> \qquad \qquad l := l_2; \ r := r_2; \\
> \qquad \textbf{end if} \\
> \qquad \textbf{if} \ l < \dfrac{|x|}{2} \land x[1, l] \ \text{为} \ x[l + 1, l + r] \ \text{的后缀} \ \textbf{then} \\
> \qquad \qquad \textbf{return} \ \text{Positions}(x, t); \\
> \qquad \textbf{else} \\
> \qquad \qquad r := \max(l, |x| - l) + 1; \\
> \qquad \qquad \textbf{return} \ \text{Positions-Large-Period}(x, t); \\
> \qquad \textbf{end if} \\
> \textbf{end function}
> \end{array}
> $$
### References
1. M. Lothaire, _Combinatorics on Words_, Cambridge Mathematical Library, Cambridge University Press, 1997 reprint of the 1983 edition, Chapter 8.
2. M. Crochemore, D. Perrin, “Two-Way String-Matching,” _Journal of the ACM_ 38(3) (1991), 650-674. <https://doi.org/10.1145/116825.116845>
3. D. Kosolobov, “Finding the Leftmost Critical Factorization on Unordered Alphabet,” _Theoretical Computer Science_ 636 (2016), 56-65. <https://www.sciencedirect.com/science/article/pii/S0304397516301104>