一切的开始
令 \(x\) 为字符串,\(p\) 为正整数. 如果对于满足 \(0\le i<|x|?p\) 的任何整数 \(i\) 满足 \(x[i]=x[i+p]\), 则 \(p\) 称为 \(x\) 的周期.\(x\) 的最小周期表示为 \(per(x)\). 例如,\(per(abcabcabcab)=3\).
令 \(N\) 为输入字符串 \(w\) 的长度. 情况划分如下:
(a)如果 \(w\) 是一个好的字符串(例如 \(w=ababa\))
(b)当 \(per(w)=1\) 时(例如 \(w=aaaaa\))
(c)其他情况(例如 \(w = abcabcabc\))
在 (a) 的情况下, 最佳表达明显为 \(1\), 最佳表达的为 \(1\).
在 (b) 的情况下, 最佳表达为 \(N\), 最佳表达的为 \(1\).
在情况 (c) 中, 我们可以证明最佳表达为 \(2\)(请参见下面的定理 \(5\)).
定理 2
由 \(\text{KMP}\) 或者 \(\text{Z-Algorithm}\) 可知, 如果正整数 \(p,q\) 是字符串 \(x\) 的周期, 且 \(p+q-\gcd(p,q)\le |x|\), 则 \(gcd(p,q)\) 也是 \(x\) 的周期.
引理 3
令 \(x\) 为非空字符串, 以下两个是等效的.
(i) \(x\) 不是好的字符串
(ii) \(|x|/per(x)\) 为 \(2\) 或更大的整数.
首先, 如果 (ii) 成立, 那么 (i) 肯定成立, 所以在下文中 (i) 就是 (ii) .
如果 \(x\) 不是一个好的字符串,\(|x|/per(x)\ge 2\) 从定义来说显而易见. 接下来我们只需要证明 \(|x|/per(x)\) 是一个整数,\(x\) 不是一个好的字符串意味着存在一个字符串 \(y\) 和一个整数 \(k\ge 2\), 使得 \(x\) 是 \(y\) 重复 \(k\) 次后获得的字符串. 令 \(p=per(x),q=|y|\), 则 \(p\le q=|x|/k\le |x|/2\), 由于 \(p,q\) 都是 \(x\) 的周期, 且满足 \(p+q-\gcd(p,q)\le |x|\), 由定理 \(2\) 知,\(\gcd(p,q)\) 是 \(x\) 的周期, 假设 \(|x|/per(x)\) 不是整数, 则 \(q\) 不是 \(p\) 的倍数, 此时 \(\gcd(p,q)<p\), 这与 \(p=per(x)\) 是 \(x\) 的最小周期相悖, 因此 \(|x|/per(x)\) 是一个整数.
引理 4
令 \(x\) 为长度为 \(2\) 或更大的字符串. 令 \(m=|x|\). 此外, 令 \(y=x [1...m ? 1]\). 如果 \(x\) 不是一个好的字符串, 并且 \(per(x)\not=1\), 则 \(y\) 是一个好的字符串.
假设 \(y\) 不是一个好的字符串. 令 \(p=per(x),q=per(y)\). 根据引理 \(3\) 和之前的假设,\(p\) 是 \(m\) 的约数,\(q\) 是 \(|y|=m-1\) 的约数. 因为 \(m\) 与 \(m-1\) 互质, 因此 \(p\) 与 \(q\) 也互质, 即 \(\gcd(p,q)=1\), 此外,\(p\le m/2,q\le(m-1)/2\), 其中 \(p\) 也是 \(y\) 的周期, 因此, 根据定理 \(2\),\(\gcd(p,q)=1\) 是 \(y\) 的周期, 因此从 \(x[0]=x[p]\) 开始,\(x\) 的最后 \(m-1\) 个字符全部变为与 \(x[0]\) 相同的字符, 此时 \(per(x)=1\), 这与前提矛盾, 故 \(y\) 是一个好的字符串.
定理 5
对于一个字符串 \(w\), 假设 \(w\) 不是一个好的字符串, 并且 \(per(w)\not=1\). 此时,\(w\)的最佳表达为 \(2\).
长度为 \(1\) 的字符串显然是一个好的字符串. 此外, 根据引理 \(4\),\(w[1...|w|?1]\) 是一个好的字符串, 因此序列 \((w [0],w[1...|w|-1])\) 是 \(w\) 是最佳表达之一. 显然,\(w\) 没有 1 或更小的最佳表达. 则 \(w\) 的最佳表达为 2.
来源: http://www.bubuko.com/infodetail-3218748.html