数据结构（6）：串（下）

上一回，我们看到串的定义和基本操作，这一会，我们看到串的一个典型应用——模式匹配！

简单的模式匹配算法

子串的定位操作通常称为串的模式匹配，它求的是子串（常称模式串）在主串中的位置。下面给出一种不依赖于其他串操作的暴力匹配算法。

def index(s, t):
    i, j = 1, 1
    while i <= len(s) and j <= len(t):
        if s[i-1] == t[j-1]:
            i += 1
            j += 1  # 继续比较后继字符
        else:
            i, j = i-j+2, 1  # 指针后退重新开始匹配
    return i-len(t)if j > len(t)else 0

在上述算法中，分别用计数指针 i 和 j 指示主串 s 和模式串 t 中当前正待比较的字符位置。算法思想为：从主串 s 的第 1 个字符起，与模式 t 中的第 1 个字符比较，若相等，则继续逐个比较后续字符；否则从主串的下一个字符起，重新和模式的字符比较；以此类推，直至模式 t 中的每个字符依次和主串 s 中的一个连续的字符序列相等，则称匹配成功，函数值为与模式 t 中的第 1 个字符相等的字符在主串 s 中的序号，否则称匹配不成功，函数值为 0。下图展示了模式 t='abcac'和主串 s='ababcabcacbab'的匹配过程，每次匹配失败后，都把模式 t 后移 1 位。

暴力匹配算法的最坏时间复杂度为 O(mn)，其中 n 和 m 分别为主串和模式串的长度。

改进的模式匹配算法——KMP 算法

上图的匹配过程，在第 3 趟匹配中，i=7、j=5 的字符比较不等，于是又从 i=4、j=1 重新开始比较。然而，仔细观察会发现，i=4 和 j=1，i=5 和 j=1 及 i=6 和 j=1 这 3 次比较都是不必进行的，因为从第 3 次部分匹配结果可知，主串中第 4、5 和 6 个字符是'b'、'c' 和 'a'。因为模式中第 1 个字符是'a'，因此它无需再和这 3 个字符进行比较，而仅需将模式向右滑动 3 个字符的位置继续进行 i=7、j=2 时的字符比较即可。

在暴力匹配中，每趟匹配失败都是模式后移 1 位再从头开始比较。而某 次已匹配相等的字符序列是模式的某个前缀，这种频繁的重复比较相当于模式串在不断地进行自我比较，这就是其低效率的根源。因此，可以从分析模式本身的结构着手，如果已匹配相等的前缀序列中有某个后缀正好是模式的前缀，那么就可以将模式向右滑动到与这些字符对齐的位置，主串 i 指针无需回溯，并继续从该位置开始进行比较。而模式向右滑动的位数的计算仅与模式本身的结构有关，与主串无关（在这里理解起来会比较困难，没关系，带着这个问题继续往后看）。

字符串的前缀、后缀和部分匹配值

要了解子串的结构，首先要弄清楚几个概念：前缀、后缀和部分匹配值。前缀指除最后一个字符以外，字符串的所有头部子串；后缀指除第 1 个字符外，字符串的所有尾部子串；部分匹配值则为字符串的前缀和后缀的最长相等前后缀长度。下面以'ababa'为例进行说明：

• 'a'的前缀和后缀都是空集合，最长相等前后缀长度为 0。
• 'ab'的前缀为{a}，后缀为{b}，{a}∩{b}=∅，最长相等前后缀长度为 0。
• 'aba'的前缀为{a,ab}，后缀为{a,ba}，{a,ab}∩{a,ba}={a}，最长相等前后缀长度为 1。
• 'abab'前缀{a,ab,aba}∩后缀{b,ab,bab}={ab}，最长相等前后缀长度为 2。
• 'ababa'前缀{a,ab,aba,abab}∩后缀{a,ba,aba,baba}={a,aba}，公共元素有 2 个，最长相等前后缀长度为 3。

故字符串'ababa'的部分匹配值为 0 0 1 2 3。

这个部分匹配值有什么作用呢？

回到最初的问题，主串为 a b a b c a b c a c b a b，子串为 a b c a c。

利用上述方法容易写出子串'abcac'的部分匹配值为 0 0 0 1 0，将部分匹配值写成数组形式，就得到了部分匹配值（Partial Match，PM）的表。

编号	1	2	3	4	5
s	a	b	c	a	c
PM	0	0	0	1	0

下面用 PM 表来进行字符串匹配：

主串

a

b

a

b

c

a

b

c

a

c

b

a

b

子串

a

b

c

第 1 趟匹配过程：

发现 c 与 a 不匹配，前面的 2 个字符'ab' 是匹配的，查表可知，最后一个字符 b 对应的部分匹配值为 0，因此按照下面的公式算出子串需要向后移动的位数：

移动位数=已匹配的字符数-对应的部分匹配值

因为 2-0=2，所以将子串向后移动 2 位，如下进行第 2 次匹配：

主串

a

b

a

b

c

a

b

c

a

c

b

a

b

子串

a

b

c

a

c

第 2 趟匹配过程：

发现 c 与 b 不匹配，前面 4 个字符'abca'是匹配的，最后一个字符 a 对应的部分匹配值为 1，4-1=3，将子串向后移动 3 位，如下进行第 3 次匹配：

主串

a

b

a

b

c

a

b

c

a

c

b

a

b

子串

a

b

c

a

c

第 3 趟匹配过程：

子串全部比较完成，匹配成功。整个匹配过程中，主串始终没有回退，故 KMP 算法可以在 O(m+n)的时间数量级上完成串的模式匹配操作，大大提高了匹配效率。

某次发生失配时，如果对应的部分匹配值为 0，即已匹配相等序列中没有相等的前后缀，此时移动的位数最大，直接将子串首字符右移到主串 i 位置进行下一趟比较；如果已匹配相等序列中存在最大相等前后缀（可理解为首尾重合），那么将子串向右滑动到和该相等前后缀对齐（这部分字符下一次显然不需要比较），然后再从主串 i 位置进行下一趟比较。

KMP 算法的原理是什么？

我们刚刚学会了怎样计算字符串的部分匹配值、怎样利用子串的部分匹配值快速的进行字符串匹配操作，但公式“移动位数=已匹配的字符数-对应的部分匹配值”的意义是什么呢？

如表 1 所示，当 c 与 b 不匹配时，已匹配 'abca' 的前缀 a 和后缀 a 为最长公共元素。已知前缀 a 与 b、c 均不同，与后缀 a 相同，故无须比较，直接将子串移动“已匹配的字符数-对应的部分匹配值”，用子串前缀后面的元素与主串匹配失败的元素开始比较即可，如表 2 所示。

表 1：失配后移动情况

主串

a

b

a

b

c

a

b

c

a

c

b

a

b

a

b

c

a

c

a

b

c

a

c

a

b

c

a

c

a

b

c

a

c

表 2：直接移动到合适的位置

主串

a

b

a

b

c

a

b

c

a

c

b

a

b

a

b

c

a

c

a

b

c

a

c

对算法的改进方法：

已知：移动位数=已匹配的字符数-对应的部分匹配值。

写成：Move=(j-1)-PM[j-1]。

使用部分匹配值时，每当匹配失败，就去找它前一个元素的部分匹配值，这样使用起来有些不方便，所以将 PM 表右移 1 位，这样哪个元素匹配失败，直接看它自己的部分匹配值即可。

将上例中的字符串'abcac'的 PM 表右移 1 位，就得到了 next 数组：

编号	1	2	3	4	5
s	a	b	c	a	c
next	-1	0	0	0	1

我们注意到：

1. 第 1 个元素右移以后的空缺用 -1 来填充，因为若是第 1 个元素匹配失败，则需要将子串向右移动 1 位，而不需要计算子串移动的位数。
2. 最后一个元素在右移过程中溢出，因为原来的子串中，最后一个元素的部分匹配值是其下一个元素使用的，但显然已没有下一个元素，故可以舍去。

这样，上式就改写为：

Move=(j-1)-next[j]

相当于将子串的比较指针 j 回退到

j=j-Move=j-((j-1)-next[j])=next[j]+1

有时为了使公式更加简洁、计算简单，将 next 数组整体+1。

因此上述子串的 next 数组也可以写成

编号	1	2	3	4	5
s	a	b	c	a	c
next	0	1	1	1	2

最终得到子串指针变化公式 j=next[j]。在实际匹配过程中，子串在内存里是不会移动的，而是指针在变化。next[j]的含义是：在子串的第 j 个字符与主串发生失配时，则跳到子串的 next[j]位置重新与主串当前位置进行比较。

如何推理 next 数组的一般公式？设主串为

模式串为

当主串中第 i 个字符与模式串中第 j 个字符失配时，子串应向右滑动多远，然后与模式中的哪个字符比较？

假设此时应与模式中的第 k（k<j）个字符继续比较，则模式中前 k-1 个字符的子串必须满足下列条件（不存在 k'>k）：

若存在满足上述条件的子串，则发生失配时，仅需将模式向右滑动至模式中第 k 个字符和主串的第 i 个字符对齐，此时模式中前 k-1 个字符的子串必定与主串中第 i 个字符之前长度为 k-1 的子串相等，由此，只需从模式第 k 个字符与主串第 i 个字符继续比较即可，如图所示。

当模式串已匹配相等字符序列中不存在满足上述条件的子串时（可以看成 k=1），显然应该将字符串右移 j-1 位，让主串第 i 个字符和模式第 1 个字符进行比较，此时右移位数最大。

当模式串第 1 个字符（j=1）与主串第 i 个字符发生失配时，规定 next[1]=0（可理解为将主串第 i 个字符和模式串第 1 个字符的前面空位置对齐，也即模式串右移 1 位。）。将模式串右移 1 位，从主串的下一个位置（i+1）和模式串的第一个字符继续比较。

通过上述分析可以得出 next 函数的公式：

上述公式不难理解，手工求 next 值时，用之前的方法也很好求，但如果想用代码实现，貌似难度还真不小，我们来尝试推理求解的科学步骤。

首先有公式可知

next[1]=0

设 next[j]=k，此时 k 应满足的条件在上文中已描述。

此时 next[j+1]=？可能有 2 种情况：

1. 若 p[k]=p[j]，则表明在模式串中'p[1]...p[k-1]p[k]'='p[j-k+1]...p[j-1]p[j]'并且不存在 k'>k 满足上述条件。此时 next[j+1]=k+1，即 next[j+1]=next[j]+1。
2. 若p[k]≠p[j]，则表明在模式串中'p[1]...p[k-1]p[k]'≠'p[j-k+1]...p[j-1]p[j]'。
   此时可以把求 next 函数值的问题视为一个模式匹配问题。用前缀

去跟后缀

匹配，则当

时应将

向右滑动至第 next[k]个字符和

比较，如果

与

还是不匹配，那么需要寻找长度更短的相等前后缀，下一步继续用

与

比较，以此类推，直到找到某个更小的 k'=next[next...[k]]（1<k'<k<j），满足条件

则 next[j+1]=k'+1。

也可能不存在任何 k'满足上述条件，即不存在长度更短的相等前缀后缀，令 next[j+1]=1。理解起来有一点费劲？下面举一个简单的例子。

求模式串的 next 值

j	1	2	3	4	5	6	7	8	9
模式	a	b	a	a	b	c	a	b	a
next[j]	0	1	1	2	2	3	？	？	？

表的模式串中以求得 6 个字符的 next 值，现在求 next[7]，因为 next[6]=3，又

则需比较

和

（因 next[3]=1），由于

而 next[1]=0，所以 next[7]=1；求 next[8]，因

则 next[8]=next[7]+1=2；求 next[9]，因

则 next[9]=3。

通过上述分析写出求 next 值的程序如下：

def get_next(t):
    i, j, nex = 1, 0, [0]*len(t)
    while i < len(t):
        if j == 0 or t[i-1] == t[j-1]:
            i += 1
            j += 1
            nex[i-1] = j  # 若 p[i]=p[j]，则 next[j+1]=next[j]+1
        else:
            j = nex[j-1]  # 否则令 j=next[j]，循环继续
    return nex

计算机执行起来效率很高，但对于手工计算来说会很困难。因此，当需要手工计算时，依然还是用最初的方法。

与 next 数组的求解相比，KMP 的匹配算法相对要简单很多，它在形式上与简单的模式匹配算法很相似。不同之处仅在于当匹配过程产生失配时，指针 i 不变，指针 j 退回到 next[j]的位置并重新进行比较，并且当指针 j 为 0 时，指针 i 和 j 同时加 1。即若主串的第 i 个位置和模式串的第 1 个字符不等，则应从主串第 i+1 个位置开始匹配，具体代码如下：

def index_kmp(s, t, nex):
    i, j = 1, 1
    while i <= len(s) and j <= len(t):
        if j == 0 or s[i-1] == t[j-1]:
            i += 1
            j += 1  # 继续比较后继字符
        else:
            j = nex[j-1]  # 模式串向右移动
    if j > len(t):
        return i-len(t)  # 匹配成功
    else:
        return 0

尽管普通模式匹配的时间复杂度是 O(mn)，KMP 算法的时间复杂度是 O(m+n)，但在一般情况下，普通模式匹配算法的实际执行时间近似于 O(m+n)，因此至今仍被采用。KMP 算法仅在主串与子串有很多“部分匹配”时才显得比普通算法快得多，其主要优点是主串不回溯。

KMP 算法的进一步优化

前面定义的 next 数组在某些情况下尚有缺陷，还可以进一步优化。如表所示，模式'aaab'在和主串'aaabaaaaab'进行匹配时：

KMP 算法进一步优化示例

主串	a	a	a	b	a	a	a	a	a	b
模式	a	a	a	a	b
j	1	2	3	4	5
next[j]	0	1	2	3	4
nextval[j]	0	0	0	0	4

当 i=4、j=4 时，

跟

（b≠a）失配，如果用之前的 next 数组还需进行

与

、

与

、

与

这 3 次比较。事实上，因为

、

、

显然后面 3 次用一个和

相同的字符跟

比较毫无意义，必然失配。那么问题出在哪里呢？

问题在于不应该出现

理由是：当

时，下次必然是

跟

比较，如果

那么相当于拿一个和

相等的字符跟

比较，这必然导致继续失配，这样的比较毫无意义。那么如果出现了

应该如何处理呢？

如果出现了，则需要再次递归，将 next[j]修正为 next[next[j]]，直至两者不相等为止，更新后的数组命名为 nextval。计算 next 数组修正值的算法如下，此时匹配算法不变。

def get_nextval(t):
    i, j, nextval = 1, 0, [0]*len(t)
    while i < len(t):
        if j == 0 or t[i-1] == t[j-1]:
            i += 1
            j += 1
            if t[i-1] != t[j-1]:
                nextval[i-1] = j
            else:
                nextval[i-1] = nextval[j-1]
        else:
            j = nextval[j-1]
    return nextval

KMP 算法对于初学者来说可能不太容易理解，可以尝试多读几遍本文的内容，并参考一些其他资料的相关内容来巩固这个。

因为考研复试已经尘埃落定（已被拟录取），数据结构系列暂时停止更新！后期会随便更新一些东西！