前言

看见字符串问题就头疼

定义

1. 周期（循环节）：

   若 $0<p \leq\mid s\mid , s[i]=s[i+p], \forall i \in\{1, \cdots,\mid s\mid-p\},$ 就称 $p$ 是 $s$ 的周期 (period)。

2. border：

   若 $0 \leq r<\mid s\mid, \operatorname{pre}(s, r)=\operatorname{suf}(s, r),$ 就称 $\operatorname{pre}(s, r)$ 是 $s$ 的border。

显然，若$pre(s,r)$是$s$的border，则$\mid s\mid - r$是$s$的周期。

Weak Periodicity Lemma

若$p$和$q$是字符串$s$的周期，且$p+q\le \mid s\mid$，则$abs(p-q)$，$gcd(p,q)$也是$s$的周期。

证明如下：

令$p>q$，设$d=p-q$，则对于任意$i\in\{1,2,\cdots,\mid s\mid\}$

• $i>p$，则$s[i]=s[i-p]=s[i-p+q]=s[i-d]$
• $i\le p$，则$i+q\le\mid S\mid$，故$s[i]=s[i+q]=s[i+q-p]=s[i-d]$

因此，$d$也是$s$的周期。

不断递归，可知$gcd(p,q)$也是$s$的周期。

Periodicity Lemma

若$p$和$q$是$s$的周期，$p+q-gcd(p,q)\le\mid s\mid$，则$gcd(p,q)$也是$s$的周期。

证明如下：

不会，请自行查阅本文 (opens new window)