串及KMP算法

串的基本概念

C、C#、java等高级语言中均有字符串这个数据类型。所谓串（或字符串），是指由零个或多个字符组成的有限序列。我们可以发现串是一种线性表，其逻辑表示为“a1a2…an”，其中ai（1≤i≤n）代表一个字符。

（1）串相等

当且仅当两个串的长度相等并且各个对应位置上的字符都相同时，这两个串才是相等的。如：

所有空串是相等的。

（2）子串

一个串中任意个连续字符组成的子序列（含空串）称为该串的子串。如：“abcde”的子串有：“”、“a”、“b”、“c”、“d”、“e”、“ab”、“bc”、“cd”、“de”、“abc”和“abcde”等。

（3）真子串

真子串是指不包含自身的所有子串。

串的存储结构

串中元素逻辑关系与线性表的相同，因此说，串可以采用与线性表相同的存储结构。

（1）串的顺序存储

串的顺序存储主要有两种实现方式：

每个单元(含多个字节)只存一个字符，称为非紧缩格式（其存储密度小）；

每个单元存放多个字符，称为紧缩格式（其存储密度大）。

（2）串的链表存储

链串的组织形式与一般的链表类似。链串中的一个结点可以存储多个字符。通常将链串中每个结点所存储的字符个数称为结点大小。

因为串可以看做是字符类型的线性表，所以顺序串中实现串的基本运算与顺序表的基本运算类似，链串中实现串的基本运算与单链表的基本运算类似，这里将不再赘述，线性表内容请看我公众号算法简堂往期文章。

模式匹配

判断模式串t是否是目标串s的子串，称为模式匹配。若是，则指在目标串s中找到一段与模式串t相同的片段（即t是s的子串），返回t在s中的起始位置；若否，则指目标串s中不存在与模式串t相同的片段（即t不是s的子串），返回-1。

（1）BF算法

Brute-Force简称为BF算法，亦称简单匹配算法。采用穷举的思路，即从s的每一个字符开始依次与t的字符进行匹配，具体匹配过程（以目标串为ACABAABAABCACAABC，模式串为ABAABCAC为例）如下动图所示：

缺陷：BF算法在字符比较时，若不相等，需要退到目标串s的当前轮匹配开始时的那个字符的下一个字符重新开始匹配；其平均时间复杂度为O(n×m)。

（2）KMP算法

KMP算法是D.E.Knuth、J.H.Morris和V.R.Pratt共同提出的，简称KMP算法。该算法较BF算法有较大改进，主要是消除了目标串指针的回溯，从而使算法效率有了某种程度的提高。开始讲解前，首先看一下KMP算法的匹配过程（依旧以目标串为ACABAABAABCACAABC，模式串为ABAABCAC为例）动图：

上述动图中，next[j]是指t[j]字符前有多少个字符与t开头的字符相同。若next[j]=k，说明模式串t[j]之前有k个字符已成功匹配，下一趟应从t[k]开始匹配；若next[j]=-1，说明模式串t[j]之前没有任何用于加速匹配的信息，下一趟应从t的开头，s的下一个字符开始匹配。如下图所示，求模式串ABAABCAC的next数组：

（3）改进的KMP算法

这就是KMP算法。但是我们会发现这个算法存在如下的问题：

上述事例中，我们可以发现在从s(3)、t(2)（即i=3、j=2时）开始匹配并失败后，又从s(3)、t(1)（即i=3、j=1时）开始匹配，匹配再次失败后从s(3)、t(0)（即i=3、j=0时）开始匹配，依旧匹配失败。这个过程存在回退现象，但是这个过程是没有必要的，因为t[3]=t[2]=t[1]=t[0]='A'，都注定了匹配失败。于是有了改进的KMP算法，如下动图所示：

上述算法中，nextval数组计算方法如下所示：

END

轻松学习

给个“赞”和“在看”，是对简堂最大的支持！