C++ 算法竞赛进阶指南 kmp模式匹配算法

字符串

一、Kmp模式匹配

（1）问题描述

有两个分别叫做A和B的字符串，它们的长度分别为N,M。

求出A是否为B的子串，如果是，求出A在B中每次出现的位置（最后一位）

（2）算法描述

①def

我们定义一个next数组。形式化来说，next的第i位就是A的前缀子串和以第i位为结尾的非前缀子串可以相等的最长长度。（伪代码定义下图）

再定义一个j数组。形式化来说，j的第i位就是A的前缀子串和以第i位为结尾的B的子串可以相等的最长长度。（伪代码定义下图）

根据j的定义，我们可以知道当j数组的某一位的值为N时，A为B的子串且这次出现的最后一位为i。

②优化

显然，直接暴力next数组的复杂度并没有达到算法的要求。为了优化算法效率，我们需要进行优化。

首先，我们定义next的第i位的所有can为它的“候选项”。

引理一：next的第i位的所有can根据从大到小的排序方式，分别为j，next[j]，next[next[j]]，etc.、

//证明：当next数组的前j位和以i结尾的后j位相等时，next数组的前x位和以next[i]位结尾的x位相等，因为他们在next[i]的计算过程中重叠（形式化如下图）

以上是kmp的算法描述，下一篇中我将写一个kmp例题的题解。