KMP算法理论篇

怼烎@ 2024-03-29 16:11 77阅读 0赞

### 概述 ###

kmp算法名称的由来是创作它的三个作者名字的简写，用于解决**字符串匹配**的问题

### 准备工作 ###

我们以kmp经典问题为例，首先要学习kmp算法中相关的概念

案列：
    文本串：aabaabaaf
    模式串：aabaaf
    
    # 这里我们需要求解文本串是否包含模式串

这里我们首先要了解什么是前缀，什么是后缀，什么是最长相等前后缀以及什么是前缀表

这些概念只针对模式串~~

前缀： 包含首字母，不包含尾字母的所有子串

模式串 aabaaf 前缀有：
    a
    aa
    aab
    aaba
    aabaa

后缀：包含尾字母，不包含首字母的所有子串

模式串 aabaaf 后缀有：
    f
    af
    aaf
    baaf
    abaaf

最长相等前后缀：字符串中前缀和后缀相等的最长子串

模式串 aabaaf 中最长相等前后缀求解如下：
    a    a理论上既是前缀也是后缀，所以没有最长相等前后缀 0
    aa   前a是前缀，后a是后缀，最长相等前后缀长度 1
    aab  最长相等前后缀长度 0
    aaba 最长相等前后缀长度 1
    aabaa 最长相等前后缀长度 2
    aabaaf 最长相等前后缀长度 0
    
    这里我们模式串的最长相等前后缀是aabaa,长度为2
    同是我们由上到下得到一个序列010120，这个序列就是我们模式串的前缀表

前缀表：通过求解最长相等前后缀得出我们的前缀表为

### 原理解析 ###

上文我们掌握了相关概念并得到了前缀表，那么我们如何使用前缀表进行匹配呢？匹配过程如下：

使用模式串和文本串进行匹配，当时出现不匹配字符
    到前缀表找到前面的字符串当中最长相等前后缀
    找到其中前缀后面继续进行匹配，此时下标即为最长相等前后缀长度
    重复上述过程，最后得到结果

通常使用名为 next 或 prefix 的数组表示前缀表，为什么要叫做next数组呢？

可能就是在我们遇见冲突的地方之后，next数组会告诉我们要回退到哪里，要回到下一个位置。

### 实现方式 ###

在很多具体实现kmp算法中，会把前缀表做一个整体右移或是统一减1的操作，效果都是一样的，都是初始位置变成-1，后面要不就是整体右移要不就是整体减1。 有一种实现kmp代码的风格在统一减1了之后，在匹配的过程还会把1加回来。无论是右移还是减1都是kmp算法的具体实现，并不涉及原理。 其实就用前缀表原封不动作为我们的next数组依然可以完成kmp算法的工作。

前缀表010120作为next数组 [0,1,0,1,2,0]
    前缀表010120整体-1作为next数组 [-1,0,-1,0,1,-1]
    前缀表010120右移作为next数组 [-1,0,1，0,2]

### 代码实现 ###

这里我们仅仅实现如何求解前缀表

如下步骤：

初始化
    前后缀不相同
    前后缀相同
    next赋值/更新

定义方法，s模式串，next数组，i后缀末尾，j前缀末尾，同是j还代表i之前包括i的最长相等前后缀

void getNext(next, s){
     j=0;
     next[0]=0; //数组在0的位置也是回退到0
     for(i=1;i<s.size;i++){
         while(j>0&&s[i]!=s[j]){
             j=next[j-1]   //遇见冲突前一位所对应的值就是我们坚持的不变量
         }
         if(s[i]==s[j]{
             j++;
             next[i]=j;
         }
     }
 }