教程 字符串

循环节与Border

前置技能 (Prerequisites)

• $KMP$

定义 (Definitions)

• 下标从 $0$ 开始
• 区间为左闭右开 $[a,b)$
• 循环节: 这里用举例来代替严格定义
  $$S[0,x)是S的循环节 \iff (\forall \ i \ S[i] = S[i\ mod\ x]) \land (x<|S|)$$
  字符串 $abcabcab$ 的循环节包括$\{abc,abcabc\}$
  注1: 原串的长度不需要是循环节长度的倍数
  注2: 本文忽略 $trivial$ 的循环节,即原串本身
• $Border:$ 一个串的 $Border$ 是任意满足既是前缀也是后缀的子串
  $abcabcab$ 的 $Border$ 包括$\{abcab,ab\}$
  注: 其实就是 $KMP$ 里面最后一个位置的 $next$ 树上的所有前缀

本文目标 (Goals)

• 证明一个串的循环节与$Border$ 一一对应。并且对应的 $$len(循环节) + len(Border) = len(S)$$

正文 (Body)

本文将以字符串 $S:abcabcab$ 以及 $循环节:abc \iff Border: abcab$ 来讲解，相信通过这个例子你可以理解为什么循环节和 $Border$ 一一对应。

首先根据定义因为 $abcab$ 是 $S$ 的一个 Border,所以它既是 $S$ 的前缀也是后缀。这里我们把 $S$ 看成由两个相交的子串($Border$子串)重叠在一起所构成，即 $S[0,5) = S[3,8) = abcab$

假设 $abc$是 $S$ 的循环节，那么我们可以得到下面这个推论:

$$S[0] = S[3] = S[6] = a \\ S[1] = S[4] = S[7] = b\\ S[2] = S[5] = c$$
观察可以发现，一个循环节可以把原串分成 $len(循环节)$ 个等价类，等价关系为
$$S[a] = S[b] \iff a \equiv b \pmod {len(循环节)}$$

我们现在的已知条件是:

$$abcab 是S的Border$$
而我们现在想得到的是
$$abc是S的循环节\\ or\\ S[0] = S[3] = S[6] = a \\ S[1] = S[4] = S[7] = b\\ S[2] = S[5] = c\\ (因为这两个命题其实是等价的)$$

---

现在我们来证明这一点。首先我们根据 $abcab\in Border$ 的定义我们知道 $S[0] = S[3]$. 还记得上面我们提到原串可以由一对相等的前缀和后缀重叠而构成吗？$S[0] = S[3]$ 其实就是前缀 $abcba$ 的第$0$个字符和第$3$个字符相等，那么因为前缀和后缀相等，所以后缀的第$0$个字符和第$3$个字符同样相等。因为后缀对应着$S[3,8)$, 所以

$$S[0+3] = S[3+3] \implies S[3] = S[6]$$
又因为
$$S[0] = S[3]$$
所以其实
$$S[0] = S[3] = S[6]$$
按照同样的方法我们可以证明其余等价类里面的字符都是相等的，这样我们就证明了依照$len(Border)$对原串进行划分是正确的，从而说明了长度为$len(S)-len(Border)$的前缀确实是$S$的一个循环节。$\blacksquare$

---

感谢

感谢叉姐在OI Camp中关于字符串的讲座（好难啊TAT）

---

我是OI界非著名菜鸡ZQC, 第一次写博文，如有任何意见或者看不懂的都可以加我qq交流:709256487。如果您觉得质量比较低，还请多担待。（好久用中文写这么长的东西了好不习惯呢（╯' - ')╯︵ ┻━┻