KMP算法之代码理解

leetcode题目：28. 找出字符串中第一个匹配项的下标

KMP算法是利用next数字（最大相同前后缀使主串指针不回退的算法，其中next有好几种实现方法，本文是其中一种方法），文章主要探讨代码的实现思路，适合能手算next数组和了解KMP算法的读者。

  • 概念介绍
  1. 前缀：包含首位字符但不包含未位字符的子串
  2. 后缀：包含未位字符但不包含首位字符的子串
  3. next数组定义：当主串与模式串的某一位字符不匹配时，模式串要回退的位置
  4. next[j]：其值 = 第 j 位字符前面 j-1 位字符组成的子串的前后缀重合字符数
  • getNext函数
void getNext(int* next, const string& s) {  // 获取next数组 演示：aabaaf => next[-1,0,1,0,1,2]
    next[0] = -1;   // 默认为-1
    int i = 1,j = -1;   // 初始化i为后缀末尾，，j指向前缀末尾
    while (i < s.size()) {  
        if (j == -1 || s[i-1]==s[j]) next[i++] = ++j;
        else j = next[j];
    }
}

其大致思路如下：

KMPnext数组

可参考视频理解：https://www.bilibili.com/video/BV16X4y137qw/?spm_id_from=333.1007.top_right_bar_window_history.content.click&vd_source=b1c06588c6b8247603b9356c32a1e5b6；这位up主讲的next数组和本文不同，不同的next数组对应的KMP算法略有不同，请注意！

  • kmp算法
int strStr(const string& haystack, const string& needle) {  // needle:针；haystack:草垛
    vector<int> next(needle.size());
    int result = -1;
    getNext(&next[0], needle);
    int i = 0, j = 0;       // i指向主串待匹配字符，j指向模式串待匹配字符
    while (i < haystack.size() && j < static_cast<int>(needle.size())){ // 不能写i < haystack.size() && j 
        if (j == -1 || haystack[i] == needle[j]) {                      // < needle.size()
            i++;    // i,j对应字符相等的话都向后移，若j=-1说明newdle[0]也!=haystack[i],说明没有相同前后缀，主串i后移，
            j++;    // 模式串j回到起始字符上
        }else { // i与j指向的字符不同，找j的对应next数组
            j = next[j];
        }
    }
    if(j == needle.size()) result = i - j;
    return result;
}
  • 代码遇到的坑：
  1. kmp算法中为什么不能写i < haystack.size() && j< needle.size():

答：因为string.size()返回的是unsign_int类型，而int类型与unsign_int类型相比较，要把int类型转换为unsign_int类型，假设为8位系统：

  • 计算机内部数据的存储方式
  1. 无符号数不涉及补码：其存储直接是二进制原码，所有位共同表示数值。
  2. 有符号数存储：使用补码表示负数。
int a = -1;                 // 补码存储：11111111
unsigned int b = a;         // 解释为原码：11111111 → 255

int -1的原码为10000001，补码为11111111，int -1 被强制转换为 unsigned int 时，其二进制补码被 直接解释为无符号整数

，值为11111111(255)。所以最终出现了int -1 > unsign_int 2的情况。

可能大家说为什么使用for循环没有遇到这种情况呢？

for(int i=0;i<s.size();i++){
    ...
}   // 是因为i在循环里仅为正数，而正数的原码等于补码，故转换后值不会发生变化

解决方法：显式将unsign_int类型转换为int类型：

static_cast<int>(needle.size());