KMP算法学习记录

KMP算法要解决的问题

在暴力字符串匹配算法里匹配流程是这样：

到了模式串最后一位B匹配失败之后会回退成这个样子

i;j代表字符串和模式串当前的所在的位置。

第一次匹配：

i=5;j=5

第二次匹配：

i=1;j=0;

匹配失败之后 i进行了回退，j也进行了回退。

这个时候导致的问题就是算法时间复杂度变成了O(m*n)。

而kmp算法出现也是为了解决这个问题。

KMP的匹配如下：

第一次匹配：

i=5;j=5

第二次匹配：

i=6;j=1;

在匹配失败了之后找到重叠的部分继续比较，i并不会回退。

这样的时间复杂度就是O(m+n)。

所以KMP解决的问题就是在匹配失败之后根据已有的信息，决定字符串i+1位置和模式串的哪个位置进行匹配。

在具体实现之前需要了解以下几点kmp算法的核心概念。

kmp算法在匹配失败之后被匹配的字符串i是不回退的，需要确定的是i+1和模式字符串的那个位置匹配。

举个例子

这个时候在i=5;j=5;的位置匹配失败。那么下一步走向该是如何？

如上图所示最终走向变成i=6；j=4；

当B和A匹配失败的时候，我们可以知道匹配失败的字符串是B，还可以知道模式字符串前j-1位（ABABA），这个时候我们将B和模式字符串前j-1位组合起来得到了ABABAB,分析组合出来的字符串可以得到前后最长公共子缀是ABAB。

那就代表ABAB这俩位置和要匹配的字符串i-3，i-2,i-1，i位是匹配的，所以接下来的比较只需要将i+1和模式串的第2位比较即可（从0开始计数）

KMP就是通过分析模式串和当前匹配失败的字符串确定出最长前后缀来决定i+1和下一步要匹配的模式串的位置。

以上是 KMP算法学习记录的全部内容，来源链接： utcz.com/a/36378.html