字符串模式匹配算法KMP

引子

今天打算回顾一下字符串中的一个经典算法。这个算法的要求很简单：给出两个字符串，在其中判断一个字符串是否包含在另一个之中。这个操作通常也被称为模式匹配。其中较短的那个称为模式串（pattern），较长的那个则称为主串（text）。因此问题的核心就在于判断模式串是否为主串的一个子序列或连续子序列。举个例子来说，在主串"abcdcbaa"中查找是否存在连续出现的"cdcba"这一序列——通过观察就可以发现这个序列确实存在，并且属于该主串的一种匹配情况。这个问题非常直观易懂，在编程实现上也相对简单明了。

分析

我们对这个问题进行了抽象处理，并明确了其中包含两个主体：一个是主串变量s,另一个是模式串变量p.其中,主串变量s由多个字符依次排列组成,其表示形式为s_{1}s_{2}...s_{m};而模式串变量p则由多个字符依次排列组成,表示形式为p_{1}p_{2}...p_{n},并且满足m\geqslant n的关系.我们的目标是判断给定的模式串变量p是否是主串变量s的一个子串.为此,可以通过逐个字符比对的方式来实现这一判断.具体步骤如下:首先将模式串的第一个字符与主串的第一个字符进行比较;如果两者相等,则继续比较第二个字符;如果相等,则继续向后比较后续字符;若在某次比较中发现不匹配情况,则将模式串向右移动一位并重新开始与下一个字符的位置进行比对.为