2026《数据结构》考研复习笔记六（串的KMP算法）

前言

本文章主题思路取自leetcode中关于KMP算法的讲解，外加笔者本人的一些感悟。为了便于读者阅读方便，节省跳转的时间，在此直接粘贴leetcode的讲解内容。关于KMP的三个函数是笔者结合王道《2025数据结构》 的函数（不完全符合）总结的，其中 关于next数组的感悟写在了next函数注释中——便于快速理解其原理，方便考试快速写出next函数并且解决匹配问题

一、KMP算法详解

二、重要函数

有几个关键记忆点要注意一下：

1. next[i]存储的是下一个要匹配的字符，所以当匹配失败后j = next[j];即可直接进行下一次匹配
2. whlie循环中(j== -1||p[i]== p[j])（求next数组）(j== -1||s[i]== p[j])(s与p匹配）中：

• j==-1：子串第一个字符匹配失败，因此子串和母串都要进位
• s[i]== p[j]：子串和母串匹配成功，因此子串和母串都要进位
• 3. 如果匹配失败，则跳转到next[j]，匹配下一个字符，直到第一个字符匹配失败，跳转到-1 4. 关于next的优化：如果跳转到的next[j]和上一个匹配失败的j位置的字符一样，则没有必要匹配，直接跳转next[j]的next[next[j]]，直接在进行next数组初始化时完成该步。由于先前的next已经完成了优化，因此后面的next只需要检查当前的字符和要跳转的位置是否相同即可（动态规划）

  1.next数组

  void getNext(const string& p, vector<int>&next) {//next[i]存储的是下一个要匹配的字符，而不是最长公共前后缀的最后一个字符int i = 0;//虽然初始化为0，但是稍后便进行i++，因为第一个字符串没有公共前后缀，直接匹配失败int j = -1;//第一个字符匹配失败next[0] = -1;//如果第一个字符串匹配失败，则无法再转跳到下一个子匹配串的匹配字符，只能赋值为-1，通过while循环进行i++,j++//由此可见，求next数组的时候，本质也是一种字符串匹配while (i < p.length()) {if (j == -1 || p[i] == p[j]) {//第一个字符匹配失败或当前字符匹配成功i++; j++;//i和j变成下一个要匹配的字符next[i] = j;//记录i前面的最长公共前后缀的长度}else {j = next[j];//跳转到下一个要匹配的字符,大部分是0，表示匹配第一个字符，只有第一个字符是-1，表示彻底匹配失败}}
  }
  

  2.next数组优化

  防止子串下一个匹配字符和上一个失败匹配字符相同，直接进入下一个不同的字符位置

  void getNextVal(const string& p, vector<int>& nextVal) {int i = 0;int j = 0;nextVal[0] = -1;while (i < p.length()) {if (j == -1 || p[i] == p[j]) {i++; j++;if (p[i] != p[j])nextVal[i] = j;else nextVal[i] = nextVal[j];//防止子串下一个匹配字符和上一个失败匹配字符相同，直接进入下一个不同的字符位置}else {j = nextVal[j];}}
  }
  

  3.KMP算法

  int Kmp(const string& s, const string& p, const vector<int>& next) {int indexS = 0;int indexP = 0;while (indexS < s.length() && indexP < p.length()) {if (indexP == -1 || s[indexS] == p[indexP]) {//第一个字符匹配失败或当前字符匹配成功indexS++, indexP++;}else {indexP = next[indexP];}}if (indexP < p.length())return 0;return indexS - p.length() + 2;//返回匹配字符串的首字母在母串的位置（1<=index<=s.length())
  }