KMP算法详解-智慧文博士

KMP算法用于实现字符串匹配问题。例如查找某个字符串是否是s的子串。

我们先来看一道题

一.力扣28.找出字符串中第一个匹配项的下标

给你两个字符串haystack和needle，请你在haystack字符串中找出needle字符串的第一个匹配项的下标（下标从 0 开始）。如果needle不是haystack的一部分，则返回-1。

输入：haystack = "sadbutsad", needle = "sad"输出：0解释："sad" 在下标 0 和 6 处匹配。 第一个匹配项的下标是 0 ，所以返回 0 。

对于这种题目,我们首先想到的就是使用两个for循环,依次找每一种可能,看看能不能找到匹配的字符串

1.传统for循环

思路:

将主串T（长度为n）与模式串P（长度为m）依次对齐比较。
对齐位置i从 0 到n-m，每次比较T[i..i+m-1]与P[0..m-1]。
若某个字符不匹配，则模式串向右移动1 位，重新从头比较。

class Solution { public: int strStr(string haystack, string needle) { int n = haystack.length(); int m = needle.length(); // needle 为空字符串的情况 if (m == 0) return 0; // 主循环，尝试所有可能的起始位置 for (int i = 0; i <= n - m; i++) { int j; // 检查当前位置是否匹配 for (j = 0; j < m; j++) { if (haystack[i + j] != needle[j]) { break; } } // 如果完全匹配 if (j == m) { return i; } } //没找到就返回-1 return -1; } };

这种传统解法的时间复杂度是O(n*m),n和m分别是两个字符串的长度,对于最坏的情况,需要搜索n*m次.

那我们可不可以进行优化呢,让搜索的次数减少,以此来降低时间复杂度,当然可以,这就是KMP算法的思想

2.KMP算法

①什么是KMP算法

KMP算法用于实现字符串匹配问题。例如查找某个字符串是否是s的子串。普通方法是从s字符串的开头开始一次比较。时间复杂度O(n*m)。KMP该是该方法的优化方法。

KMP算法的核心思想,就是每次如果字符串没有匹配成功,不是从头开始重新查找,而是从一个特定的合理位置开始继续查找,减少了查找次数

那我们应该如何去找到这个特定的合理位置呢,这就是KMP算法的关键,引入一个前缀表的概念

②前缀表

前缀表：记录下标i之前（包括i）的字符串中，有多大长度的相同前缀后缀。

前缀是指不包含最后一个字符，以第一个字符开头的连续子串。

后缀是指不包含第一个字符，以最后一个字符结尾的连续子串

前缀表要求的就是相同前后缀的长度

字符串a的最长相等前后缀为0。字符串aa的最长相等前后缀为1。字符串aaa的最长相等前后缀为2。

③next数组

KMP算法就是把子串中的每个位置对应的最长相同前后缀长度,记录在next数组中,一旦匹配失败,就从当前已匹配位置的最长前缀长度继续进行匹配(next[i-1])

④代码实现

1)构建next数组

构建next数组的过程,实际上就是子串自己进行KMP算法的过程

void getNext(vector<int>& next, string& needle) { //初始化最大前后缀长度 int j = 0; //第一个位置的字母相同前后缀长度是0 next[0] = 0; //开始循环查找 for (int i = 1;i < needle.size();i++) { //如果不同,就从已经匹配的最大位置开始重新匹配,直到匹配成功 while (j > 0 && needle[i] != needle[j]) { j = next[j - 1]; } //如果相同,就将前后缀长度+1 if (needle[i] == needle[j]) { j++; } //给当前位置赋值 next[i] = j; } }

2)查找第一个匹配项位置

int KMP(string s, string s1) { //字符串为空或者子串长度更大都是错误的 if (s1.size() == 0 || s.size() == 0 || s.size() < s1.size()) { return -1; } //初始化next数组 vector<int>next(s1.size(),0); //调用方法得到next数组 getNext(next, s1); //开始查找 int j = 0; for (int i = 0;i < s.size();i++) { //和构建next数组一样,如果不匹配,就从已匹配的最长位置重新开始 while (j > 0 && s[i] != s1[j]) { j = next[j - 1]; } //如果相同,就将已匹配长度+1 if (s[i] == s1[j]) { j++; } //终止条件是已匹配长度和子串长度相等,说明全部匹配 if (j == s1.size()) { return i - s1.size() + 1; } } return -1; }

3)举一反三

如果题目要求查找所有匹配项,就将KMP函数中查找成功的部分改为

vec.push_back(i - s1.size() + 1);//存储结果 j=next[j-1];//继续查找

4)效率分析

对于传统的双重for循环的O(n*m)的时间复杂度,KMP算法可以将其降至O(n+m),大大优化了传统方法

在最坏的情况下,如子串是ac,父串是aaa...ac时效果更加明显

3.方法比较

算法	时间复杂度	空间复杂度	优点	缺点
暴力匹配	O(n × m)	O(1)	实现简单，代码短	最坏情况下效率低
KMP	O(n + m)	O(m)	效率高，适合长字符串	实现复杂，需要额外空间