KMP字符串匹配算法

本文用于记录个人算法竞赛学习，仅供参考

一.KMP

二.next数组（前缀表）

三.具体实现模板

四.题解

先来看一个问题

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

对于这个问题，一般暴力做法是：遍历主串，以主串的每个元素为开头分别与模式串对比，遇到不匹配，主串走下一位，模式串重新开始一一对比，假设主串长度为n，模式串长度为m，那么时间复杂度是O(n * m)。

使用KMP解决这个问题时间复杂度只需要O(n + m)。

一.KMP

KMP主要用于字符串匹配的场景中，用于解决字符串匹配、重复子字符串等问题。

1.思想：当出现字符串不匹配时，可以通过一部分之已经匹配过的文本内容，利用这些信息避免从头再去匹配。

2.与暴力匹配的区别：KMP主串全程只遍历一遍，从不走回头路；每次不匹配时模式串不需要回退到起点。

能做到上述操作的主要原因是next数组的功能。

二.next数组（前缀表）

1.前缀表定义：记录下标i（包括i）之前的字符串中有多长的最长相同前后缀

前缀是不包含最后一个字符的连续子字符串；后缀是不包含第一个字符的连续子字符串。

2.前缀表的作用：用来模式串的回退，它记录了主串与模式串不匹配时模式串应该从哪里开始从新开始。

3.模拟匹配（这里是假设字符串下标是从1开始的，这样比较好实现）：

3.求next数组

记录下标i（包括i）之前的字符串中有多长的最长相同前后缀，其实在实现next数组时，和主串与模式串匹配大差不差；

因为第一个位置既不能是前缀又不能是后缀，所以第一位（下标1）是0，直接跳过第一位从第二位开始求next数组；

现在可以将模式串看成是两个串，一个是从第二位开始的“主串”，一个是从第一位开始的“模式串”，为什么可以这样想，因为在第一位不存在前后缀，形成前后缀至少需要两个字符，这就形成了错位，后缀在后，前缀在前，求next数组就是求最长相同前后缀，这个过程相当于前缀与后缀在做匹配的过程。

三.具体实现模板

很多人都感觉KMP难以理解，是因为实现方式有很多种，都没有同一的实现方式，使很多人查找资料将多种解释混在一起就晕了。

这里先将实现细节约定熟成：

主串，模式串都是下标从1开始的字符串，这样好处理边界条件，next数组也是从下标1开始才有数据的。

//KMP伪代码

//s[] 是主串， p[] 是模式串， n 是主串长度， m 是模式串长度
//主串，模式串，next 数组都是下标从1开始才有 有效数据的

//求next数组
for (int i = 2, j = 0; i <= m; i++)
{
	while (j && p[i] != p[j + 1])
		j = next[j];
	if (p[i] == p[j + 1])
		j++;
	next[i] = j;
}

//匹配
for (int i = 1,j = 0; i <= n; i++)
{
	//回退
	while (j && s[i] != p[j + 1])
		j = next[j];
	if (s[i] == p[j + 1])
		j++;
	if (j == m)//模式串遍历完
	{
		j = next[j];
		//查找成功后的逻辑
	}
}

四.题解

所以开头的问题可以直接套用公式

class Solution {
public:
    int strStr(string haystack, string needle) {
        haystack.insert(0, 1, '0');
        needle.insert(0, 1, '0');
        int n = haystack.size() - 1;
        int m = needle.size() - 1;
        vector<int> next(m + 1);
        //求next数组
        for(int i = 2, j = 0; i <= m; i++)
        {
            while(j && needle[i] != needle[j + 1])
                j = next[j];
            if(needle[i] == needle[j + 1])
                j++;
            next[i] = j;
        }
        //匹配
        for(int i = 1, j = 0; i <= n; i++)
        {
            //回退
            while(j && haystack[i] != needle[j + 1])
                j = next[j];
            if(haystack[i] == needle[j + 1])
                j++;
            if(j == m)
            {
                return i - m;
            }
        }
        return -1;
    }
};