字符串的组合性质学习笔记

算法

摘要：本文主要给出字符串的定义和若干简单组合性质的证明，并简要分析字符串相关算法。

1. 基本定义

定义1.1： 由有限字母表 $\Sigma$ 中元素构成的数组P[1..m]称为一个字符串，m称为字符串的长度，记作 $|P|$。记 $\Sigma^*$ 是该字母表下所有有限字符串构成的的集合。如果 $|S| = 0$ ，记 $S = \emptyset。$

定义1.2： 对于两个字符串A, S，如果 $|A| \le |S|$ 且 $\forall 1 \le i \le |A|, A[i] = S[i]$，称A为S的前缀，记作 $A\sqsubset S$，或 $A = S_{|A|}$ 。对于两个字符串B, S，如果 $|B| \le |S|$ 且 $\forall |S|-|B|+1 \le i \le |S|, B[i] = S[i]$，称B为S的后缀，记作 $B\sqsupset S$，或 $B = S_{-|A|}$ 。

引理1.1： $\sqsubset，\sqsupset$ 都是等价关系。

证明：显然。

引理1.2(前缀、后缀重叠引理)： 对于字符串S的两个前缀$S_i, S_j$，$S_i\sqsubset S_j \iff i\le j$，对于两个后缀$S_{-p}, S_{-q}, S_{-p}\sqsupset S_{-q}\iff p\le q。$

证明：显然。

定义1.3：两个字符串$S_1, S_2$的连接$S_1S_2 = P, P_{|S_1|} = S_1, P_{-|S_2|} = S_2$。记$SSSS\dots SS(k个) = S^k$

引理1.3： 群 $(\Sigma^ * ,\circ, \emptyset)$ 同态于非负整数加群。

证明：显然。

2. Border与周期

定义2.1： 对于一个字符串S，如果 $S_i = S_{-i}$，称$S_i$为S的一个border。S所有border中长度最长且不为其本身的称为其最长非平凡border，记作 $\pi(S)$。

引理2.1(border的传递性)： A是B的border，B是C的border，则A是C的border。

证明：显然。

引理2.2： $\pi(\pi(S))(\ne \emptyset)$ 是S的第二长非平凡border。由此可以知道，$\pi^n(S)$ 是S的第n长非平凡border。

证明：第一部分用反证法，设 $A = \pi(S), B = \pi(A)$，如果存在border$S_i$满足 $|B|<i<|A|$，由于引理1.2，$S_i\sqsubset A$。根据定义，$S_i=A_i$, 由于A为S的border，有 $A_i = S_i = S_{-i}$。由于$S_{-i}\sqsupset S, S_{-|A|}\sqsupset S, i<|A|$，因而$S_{-i}\sqsupset S_{-|A|}$，所以$S_{-i}\sqsupset S_{|A|} = A$。由于 $S_i\sqsubset A$，可知$S_i(i>|B|)$ 是A的border，与 $B=\pi(A)$ 矛盾。第二部分用归纳法，这里省略。

定义2.2： 如果S的一个前缀$S_i$，满足$S\sqsubset S_i^\infty$，称i是S的周期。

引理2.3： i是S非平凡的周期 $\iff S_d(d = |S|-i)$ 是S的非平凡border。

证明：
1. $\Rightarrow：$ 考虑$S_i^\infty$与S相交的形态，设k为满足$S\sqsubset S_i^k$的最小正整数，则 $S = S_i^{k-1}(S_i)_ p = S_i^{k-1}S_p, (p=|S_i|-(|S_i^k|-|S|))$，设 $T = S_i^{k-2}S_p$ 则显然$T\sqsupset S$。由于$p<i, 所以S_p\sqsubset S_i, 因而T = S_i^{k-2}S_p \sqsubset S_i^{k-2}S_i=S_i^{k-1}\sqsubset S$, 因而T为S的border；
2. $\Leftarrow：$ border长度长于字符串一半时：

S_i:                 |--s4--|
S_i:          |--s2--|
Border:       |---------|
S:     |----------------|
Border:|---------|
S_i:   |--s1--|
S_i:          |--s3--|

• 按照s1, s2...不难证明其是S的周期。border长度短于字符串一半时则是显然的：

Border:            |-s2-|
S:     |----------------|
Border:|-s1-|
P:     |-S1-|------|-s2-|------|
P:     |-----------|-----------|

定理2.4(弱周期定理)： p和q是S的周期，满足 $p+q\le |S|$ 则 $gcd(p, q)$ 为S的周期。

证明：令$p< q即|S|-p>|S|-q$，根据更相减损术的证明我们知道，只需要证明q-p为S的周期即可。由引理2.2可以知道$S_{|S|-p}, S_{|S|-q}$ 是S的border。设$d = q-p$，由于$p+q\le |S|$，故两个周期不能都大于字符串一半长，两个border不能都小于字符串一半长。由于$S_{|S|-q}$是$S_{|S|-p}$的border，那么$\forall k\le |S|-q, S[k] = S[d+k]$；同理$S_{-t(t=|S|-q)}$是$S_{-h(h=|S|-p)}$的border，那么$\forall p\le k\le p+|S|-q, S[k] = S[d+k]$。由于$p+q\le|S|, |S|-q\ge p$，则$\forall k\le |S|-q+p = |S|-d, S[k] = S[d+k]$。根据定义可以知道$S_{|S|-d}$是S的border，根据引理2.3，d是S的周期。

弱周期定理是一个强大的定理，在很多证明中我们都要用到，请读者认真理解。

推论2.5： 不小于字符串一半长的border长度成等差数列；小于字符串一半长的周期长度成等差数列，且公差等于最小的周期长。

证明：两命题等价，我们只证明第二个。取最小的周期长$i$，则对于任意一个周期$k$满足$i\le k \le \frac {|S|} 2$，根据弱周期定理，$gcd(i, k)$也是周期，因为i是最小周期，$gcd(i, k) \ge i$，则$gcd(i, k) = i即i|k$。接着我们只需要证明$\forall k \le \frac {|S|} 2且i|k$，都有k是周期，这是显然的，因为只需要将$S_i$重复$\frac k i$次便可以得到$S_k$，其显然为周期。

定理2.6： 一个字符串所有的border可以被划分成$O(\lg n)$段等差数列；一个字符串所有的周期可以被划分成$O(\lg n)$段等差数列。

证明：考虑将字符串|S|所有border按长度划分为$[2^0, 2^1), [2^1, 2^2),\dots,[2^k, 2^{k+1}), [2^{k+1}, |S|]$。根据推论2.5，最后一段中是正确的。对于$i\le k$，考虑长度在$[2^i, 2^{i+1})$的border长为$a_1, a_2,\dots ,a_p满足2^i\le a_1\le a_2 \le...\le a_p < 2^{i+1}$，则$\forall 1\le j\le p, S_j是S_p$的长度大于一半的border，成等差数列，第一个命题得证。根据引理2.3不难证明第二个命题。

算法2.1：快速计算前缀的$\pi(x)$

我们定义$\pi_S(x)$为$|\pi(S_x)|$，下面的算法可以计算出所有前缀的最长非平凡border。

void calc_pi(int pi[], char str[], int len)
{
    pi[1] = 0;
    int j = 0;
    for (int i = 2; i <= len; i++) {
        while (j && str[j+1] != str[i]) i = pi[i];
        if (str[j+1] == str[i]) ++j;
        pi[i] = j;
    }
}

正确性：核心在于算法第6行，即如果$S_i是S_{|S|-1}$的border且$S_{i+1}$不是S的border，那么$\forall \pi_S(i)<x< i, S_{x+1}$都不是S的border。我们用反证法，假设$\exists \pi_S(i)<x< i, S_{x+1}$是S的border，则$S_x$是$S_{|S|-1}$的border，也是$S_i$的border，和$\pi_S(x)$的定义矛盾。

时间复杂度：由于j的增加只出现在第7行，而6行的while循环则会使j减小，由于增加最多为|S|，因而while循环运行次数为$O(|S|)$，总复杂度为$\Theta (S)$。

定义2.3： 对于两个字符串P, S，如果S存在一个后缀$S_{-i}$满足$P\sqsubset S_{-i}$，称P在$|S|-i+1$的位置匹配了S。

定理2.4： 如果$|P| \le \frac {|S|} 2$，则P对S所有匹配的位置成一等差数列。

证明：我们取最小的匹配位置i和第二小匹配位置j，对于之后任意一个匹配位置k，由于$|P| \le \frac {|S|} 2$任意两个匹配都相交。

S:   |--------------------|
P1:   i----P1-----|
P2:     j----P2-----|
P3:           k----P3-----|

由于P1是$P1\cup P2$的border，因而j-i是$P1\cup P2$的周期；由于P1是$P1\cup P3$的border，k-i是$P1\cup P3$的周期，因而也是$P1\cup P2$的周期。根据弱周期引理，$gcd(j-i, k-i)$ 也是$P1\cup P2$的周期。如果j-i不是$P1\cup P2$的最小周期，设最小周期为u，则有最长border Px, $|Px| = |P1\cup P2|-u$：

S:   |--------------------|
P1:   i----P1-----|
Px:   ------Px-----|
Px2:   |-----Px2---|
Px:    |------Px-----
P2:     j----P2-----|
P3:           k----P3-----|

观察到Px相交的区域包含一个$Px2 = Px_{|P|} = P1$也构成一个匹配，这与P2为第二小的匹配位置矛盾。因而j-i是$P1\cup P2$的最小周期。则$j-i = gcd(j-i, k-i)$即$j-i|k-i$。

下面我们只需要说明$\forall k(j-i|k-i), k$位置可以匹配：

S:   |--------------------|
P1:   i----P1-----|
P2:     j----P2-----|
P3:        p----P3-----|
P4:           k----P4-----|
...

我们在所有满足$j-i|k-i$的位置构造Px，直到最后一个匹配。以P4为最后一个为例，我们需要证明P3是一个匹配。由于P2是$P2\cup P4$的border，k-j也是其周期，则k-j也是$P2\cup P3$的周期，因而P2是$P2\cup P3$的border，P3因而也是一个匹配。用类似的构造法可以证明原命题。

算法2.2：KMP字符串匹配算法

void kmp(char S[], int Sl, char P[], int Pl, int pi_P[])
{ // pi_P[]可以由算法2.1算出
    int j = 0;
    for (int i = 1; i <= S1; i++) {
        while (j && P[j+1] != S[i]) j = pi_P[j];
        if (P[j+1] == S[i]) ++j;
        if (j == Pl) {
            printf("Matched Successfully on %d\n", i-Pl+1);
            j = pi_P[j]; // find again
        }
    }
}

算法正确性和复杂度的证明类似于算法2.1，请读者类比2.1证明之。