【KMP算法】

KMP算法用来干什么的？

• kmp算法是用来进行子串的匹配的算法。作用相当于c语言库中的strstr函数。

如何实现KMP算法？

首先我们需要看到KMP算法能够真正地解决子串的匹配问题。

比如：给一个文本串：aabaabaaf,模式串aabaaf

KMP算法的作用是从文本串中匹配出模式串。

过程如下：

• 1.文本串的a和模式串a匹配
• 2.文本串的a和模式串a匹配
• 3.文本串的b和模式串b匹配
• 4.文本串的a和模式串a匹配
• 5.文本串的a和模式串a匹配
• 6.文本串的b和模式串f不匹配
• 发现不匹配的字符后
• KMP算法会回溯到模式串的b的下标，继续和文本串的b进行匹配
• 7.文本串的b和模式串b匹配
• 8.文本串的a和模式串a匹配
• 9.文本串的a和模式串a匹配
• 10.文本串的f和模式串f匹配

匹配完成

图解过程如下：

1.前缀表的由来

首先知道什么是前缀和后缀。

前缀：字符串中只包含首字母不包含尾字母的所有子串
后缀：字符串中只包含尾字母不包含首字母的所有子串

拿上面的模式串为例子：aabaaf

它的前缀字符串为：

a

aa

aab

aaba

aabaa

它的后缀字符串为：

f

af

aaf

baaf

abaaf

而前缀表就是用来求最长相等前缀和后缀的长度

先求前缀表：

2.前后缀的匹配过程

那为什么在上面的例子中，当模式串的最后一个字母f和文本串的b不匹配时，模式串会跳到自己的b的位置重新进行匹配呢？

由前缀表可以知道，aabaa的最长相等前后缀长度为2：

说明aabaa这个字符串的最长相等后缀为aa，在它前面一定有与它相等的前缀aa对应。

图解如下：

从最后这个a位置开始再往后匹配，发现不相等了，也就是此时最长后缀的后一个字符不相同，那就回退到最长相等前缀的后一个字符继续匹配。

因为最长相等前缀的长度的后一个字符的下标就对应这最长相等前后缀的长度。

当遇到不匹配的字符时，

需要回退到该字符的前一个字符对应的前缀表数字的下标进行匹配。

也就是回退到b位置进行匹配。

3.next数组

next数组所存储的值就是前缀表存储的值。

具体实现KMP算法代码如下：

1.初始化

给一个指针i，指向后缀的末尾位置，同时代表i下标之前的一个最长字符串。

给一个指针j，指向前缀的末尾位置，同时代表最长相等前后缀长度

所以应该初始化j = 0，next[0] = 0，i = 1

2.前后缀不同的情况

假设s为文本串aabaabaaf,s1为模式串aabaaf

如果匹配的字母不相同，即：s[i] != s1[j]

就让指针j回退到next[j-1]的位置，即 j = next[j-1]

不过有一点，如果第一个字母就不匹配了，那么j-1 = -1此时的情况会出现越界，所以我们需要让j>0

//前后缀不相等的情况,回退到这个不相等的前一个字符的next值
while (j > 0 && s1[j] != s1[i])
{
  j = next[j - 1];
}

记住不能使用if，要使用while，因为可能会出现回退之后再匹配仍然不相等的情况，需要持续回退。

3.前后缀相等情况

如果对应字母匹配了，即s[i] == s1[j]，那么我们就让j++即可。

//相等情况
if (s1[j] == s1[i])
{
  j++;
}

4.更新next

不管到底是否匹配，我们都需要对next数组进行更新

next[i] = j;//j同时代表最长相等前后缀的长度。

C++版本总代码如下

class Soluction
{
public:
  void GetNext(const string& s1, int* next)
  {
    //模式串：aabaaf
    int j = 0;//j指向模式串的前缀末尾，同时j还代表最长相等前后缀长度
    int i = 1;//i指向模式串的后缀末尾,同时还代表i下标开始及其前面的字符串
    next[0] = 0;
    //1.处理前后缀不相等的情况
    //2.处理相等情况
    //3.更新next数组
    for (i = 1; i < (int)s1.size(); ++i)
    {
      //前后缀不相等的情况,回退到这个不相等的前一个字符的next值
      while (j > 0 && s1[j] != s1[i])
      {
        j = next[j - 1];
      }
      //相等情况
      if (s1[j] == s1[i])
      {
        j++;
      }
      //更新next
      next[i] = j;//将长度放进next中
    }
  }
  int is_substr(const string& s, const string& s1)
  {
    //next数组是记录模式串的最长前后缀相等长度的
    int next[6];
    GetNext(s1, next);
    int j = 0;
    //aabaabaaf
    //aabaaf
    for (int i = 0; i < (int)s.size(); ++i)
    {
      //不匹配的情况
      while (j > 0 && s1[j] != s[i])
        j = next[j - 1];
      //匹配情况
      if (s1[j] == s[i])
        j++;
      //j已经完全匹配了
      if (j == s1.size()) 
        return i - j + 1;
    }
    return -1;
  }
};

注意：

if (j == s1.size()) 
  return i - j + 1;

这个情况是j == s1.size()，而不是j == s1.size() -1，不要混淆了。

总结

使用KMP算法解决字符串的匹配问题大功告成。