概述

对于字符串这一数据结构，寻找字符串中子串的位置是最重要的操作之一，查找子串位置的操作通常称为串的模式匹配。而KMP算法就是一种字符串模式匹配算法

朴素模式匹配

在介绍KMP算法之前，首先了解朴素模式匹配如何进行

思路解析

朴素的想法是用两个指针i,j分别指向主串和子串，如果两个指针指向的元素相同则指针后移，不相同则需要回退指针(主串指针回退到上次匹配首位的下一个位置，子串指针回退到开头位置)，重复进行上述操作直到主串指针指向主串末尾

举个例子：主串S=“goodgoogle”，子串T=“google”

  1. 从主串S的第一位开始匹配，S和T的前三位都能匹配成功，第四位匹配失败，此时将主串的指针i退回到第二位，子串的指针j退回到起始位置(s[1])

kmp_1.png

  1. 主串S从第二位开始于子串T匹配，第一步就匹配失败，将主串指针指向第三位S[2]，子串指针指向开头，继续匹配

kmp_2.png

  1. 同步骤2，第一步就匹配失败，将主串指针移动到第四位S[3]，子串指针指向开头，继续匹配

kmp_3.png

  1. 还是第一步就匹配失败，将主串指针移动到第五位S[4]，子串指针指向开头，继续匹配

kmp_4.png

  1. 匹配成功！

kmp_5.png

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 朴素模式匹配算法函数
int naivePatternMatching(const std::string& text, const std::string& pattern) {
    int textLength = text.length();
    int patternLength = pattern.length();
 
    // 遍历文本的每一个可能的位置
    //之所以要减去子串的长度是因为如果主串剩下的长度小于子串总长度说明子串在接下来就不可能出现
    for (int i = 0; i <= textLength - patternLength; ++i) {
        int j;
        // 尝试在当前位置匹配整个模式
        for (j = 0; j < patternLength; ++j) {
            // 如果字符不匹配，则跳出内层循环，尝试下一个位置
            if (text[i + j] != pattern[j]) {
                break;
            }
        }
        // 如果内层循环成功完成，说明找到了一个匹配的位置
        if (j == patternLength) {
            return i; // 返回匹配的位置（从0开始计数）
        }
    }
    // 如果没有找到匹配的位置，则返回-1
    return -1;
}

算法性能

既然是暴力做法，算法的开支相对较大。朴素模式匹配算法的时间复杂度为 O((n-m+1)*m)，其中 n 是文本的长度，m 是模式的长度。在最坏的情况下（即每次匹配都失败），算法需要执行 n-m+1 次尝试，每次尝试都要比较 m 个字符

优化算法KMP

为了避免朴素算法的低效，几位计算机科学家前辈D.E.Knuth、J.H.MorTis和V.R.Pratt发表了一个模式匹配算法，可以一定程度上避免重复遍历的问题，该算法就是大名鼎鼎的KMP算法。

怎么优化？

KMP算法是朴素模式匹配的优化算法，既然这样就要知道优化在哪里。

之前的朴素算法过程如下：

kmp_6.png

从上可知，在2、3、4步骤中，主串指针i指向的字符和子串的首字符都不匹配。也就是说这几步根本不需要执行，有没有一种办法可以让子串直接移到合适的地方呢?

再举一个例子：主串S=“abcababca”，子串T=“abcabx”。按照朴素算法如下：

kmp_7.png

由之前一个例子的分析可知由于T串的首字母”a”与之后的字母”b”、”c”不等，故步骤2、3均是可以省略的。

又因为T的首位”a”与T第四位的”a”相等，第二位的”b”与第五位的”b”相等。而在步骤1中，第四位的”a”与第五位的”b”已经与主串s中的相应位置比较过了是相等的。因此可以断定, T的首字符“a”、第二位的字符“b”与S的第四位字符和第五位字符也不需要比较了，肯定也是相等的。所以步骤4、5这两个比较得出字符相等的步骤也可以省略

在这个例子中我们发现，在得知了子串中有相等的前后缀之后，匹配失败时子串指针不需要回退到开头处，而是回退到相等前缀的后一个位置

字符串的前缀就是不包含最后一个字符的所有子串，后缀就是不包含第一个字符的所有子串

算法原理

KMP引入一个额外的数组来记录如果匹配失败指针j该回溯到哪里，即next数组,记录的是字符串中的每个子串的最大相等前后缀的长度

举个例子：设字符串T=“abababab”，从下标0开始存储

  1. 当j=0，没有前缀和后缀可以比较，所以next[0]=0
  2. 当j=1，前缀“a”，后缀“b”，没有相等的前后缀，所以next[1]=0
  3. 当j=2，前缀“a”、“ab”，后缀“a”、“ba”，最长相等前后缀长度为1，所以next[2]=1
  4. 当j=3，前缀“a”、“ab”、“aba”，后缀“b”、“ab”、“bab”，最长相等前后缀长度为2，所以next[3]=2
  5. 以此类推：next[4]=3,next[5]=4,next[6]=5,next[7]=6
next 0 1 2 3 4 5 6 7
0 0 1 2 3 4 5 6

设字符串S=“abababcabababab”

很明显：S[i] != T[j + 1]

​ i

a b a b a b c a b a b a b a b

a b a b a b a b

​ j

当i=6，j=6时发生了不匹配，根据next数组next[5],将j回溯到T[4]的位置。

​ i

a b a b a b c a b a b a b a b

​ a b a b a b a b

​ j

这样就可以不动指针i而只用回溯指针j

代码实现(都从0开始存储)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int KMP(const string& s, const string& t) {
	int slength = s.size(), tlength = t.size();
	vector<int> next(tlength, 0);
    //处理next数组
	for (int i = 1, j = 0; i < tlength; i++) {
		while (j > 0 && t[i] != t[j]) j = next[j - 1];
		if (t[i] == t[j]) j++;
		next[i] = j;
	}
    //匹配
	for (int i = 0, j = 0; i < slength; i++) {
		while (j > 0 && s[i] != t[j]) j = next[j - 1];
		if (s[i] == t[j])j++;
		if (j == tlength)
			return i - j + 1;
	}
	return -1;
}

算法性能

实战例题

kmp_8.png

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int strStr(string haystack, string needle) {
        int hlength = haystack.size(), nlength = needle.size();
        vector<int> next(nlength, 0);
        //处理next数组
        for (int i = 1, j = 0; i < nlength; i++) {
            while (j > 0 && needle[i] != needle[j])
                j = next[j - 1];
            if (needle[i] == needle[j])
                j++;
            next[i] = j;
        }
        //匹配
        for (int i = 0, j = 0; i < hlength; i++) {
            while (j > 0 && haystack[i] != needle[j])
                j = next[j - 1];
            if (haystack[i] == needle[j])
                j++;
            if (j == nlength)
                return i - j + 1;
        }
        return -1;
    }
};