​ 日常网路生活中很多地方都需要用到字符匹配，最常见的如使用搜索引擎的时候。

​ 这里我们学习两种算法：朴素模式匹配算法、KMP算法。

朴素模式匹配算法

主串长度为n，模式串长度为m

朴素模式匹配算法：将主串中所有长度为m的子串依次与模式串对比，直到找到一个完全匹配的子串，或所有的子串都不匹配为止。

此时，最多拥有n-m+1个子串。这里可以类比在String的学习中学到的Index即定位操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int Index(SString S,SString T){
	int i=1,j=1;
	while(i<-Slength &&j<=T.length){
		if(s.ch[i]==T.ch[j]){
			++1;++j;//继续比较后继字符
    }
	else{
		i=i-j+2;
		j=1;//指针后退重新开始匹配
    }
	if(j>T.length)
		return i-T.length;
	else
		return 0;
}

最坏时间复杂度O(mn)；

这种算法有一个显而易见的缺点，它一旦发现不匹配，指向字符串的指针就要回溯到开始的地方重新查找，因此kmp算法诞生了

KMP算法

KMP 的关键是：当模式串匹配失败时，尽可能利用已经匹配的信息来决定下一步的匹配位置，而不是回退文本指针。

假设：

  • 文本串为 T[0..n-1]
  • 模式串为 P[0..m-1]

匹配时：

  • 如果当前字符 T[i] == P[j]，则 i++, j++
  • 否则 j = next[j]，避免重新从头匹配 P

这里最关键的就是这个next数组的确定，考研的话会考察手算next数组

next数组

定义：

next[j] 表示：在 P[0..j-1] 这个前缀中，最长的相等的前缀和后缀的长度。

也可理解为：当前 j 失配时，j 应该跳转到的位置（模式串内部的回退指针）。

构建思路（递推）：

设 j 是当前构建的位置，k = next[j - 1] 是上一位的最长前后缀长度。

  • 如果 P[j] == P[k]，说明 P[0..k] 和 P[j-k..j] 是匹配的，next[j] = k + 1
  • 否则就递归地找 next[k]，直到 k == 0 或找到匹配为止

示例：

对于模式串 P = "a b a b c a b"：

j（位置） 0 1 2 3 4 5 6
P[j] a b a b c a b
next[j] 0 0 1 2 0 1 2

解释：

  • next[2] = 1 是因为 P[0] == P[2] = a，最长相等前后缀是 “a”
  • next[4] = 0 因为 P[0..3] = abab 没有前后缀匹配
next数组的优化

当某些字符重复时，比如模式串 P = "aaaaa"，原始的 next 会导致重复匹配失败多次跳转仍然匹配到同一个字符。

nextval[j] 的定义：

当 P[j] != T[i] 且 next[j] > 0，我们跳转到 nextval[j] 而不是 next[j]，以 避免无意义的重复匹配字符。

构建规则：

1
2
3
4
5
if (P[j] == P[next[j]]) {
    nextval[j] = nextval[next[j]];
} else {
    nextval[j] = next[j];
}

或简化为：

1
2
3
4
5
if (P[j] == P[next[j]]) {
    nextval[j] = nextval[next[j]]; // 跳过重复字符
} else {
    nextval[j] = next[j];          // 保留正常跳转
}
实现

基于以上思路实现KMP算法：

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <iostream>
#include <vector>
#include <string>
using namespace std;

class KMP {
public:
    // 构建 next 数组
    vector<int> getNext(const string& pattern) {
        int m = pattern.size();
        vector<int> next(m, 0);
        int j = 0; // 当前构造的位置
        for (int i = 1; i < m; ++i) {
            while (j > 0 && pattern[i] != pattern[j]) {
                j = next[j - 1];
            }
            if (pattern[i] == pattern[j]) {
                ++j;
            }
            next[i] = j;
        }
        return next;
    }

    // 构建 nextval 数组（优化版本）
    vector<int> getNextVal(const string& pattern) {
        vector<int> next = getNext(pattern);
        vector<int> nextval = next;
        int m = pattern.size();
        for (int i = 1; i < m; ++i) {
            if (pattern[i] == pattern[next[i - 1]]) {
                nextval[i] = nextval[next[i - 1]];
            }
        }
        return nextval;
    }

    // 使用 next 或 nextval 进行 KMP 匹配
    vector<int> match(const string& text, const string& pattern, bool useNextVal = false) {
        int n = text.size(), m = pattern.size();
        vector<int> result;
        if (m == 0 || n < m) return result;

        vector<int> next = useNextVal ? getNextVal(pattern) : getNext(pattern);
        int j = 0;
        for (int i = 0; i < n; ++i) {
            while (j > 0 && text[i] != pattern[j]) {
                j = next[j - 1]; // 回退位置
            }
            if (text[i] == pattern[j]) {
                ++j;
            }
            if (j == m) {
                result.push_back(i - m + 1); // 匹配成功
                j = next[j - 1];             // 寻找下一个匹配
            }
        }
        return result;
    }
};

时间复杂度为O(n + m)，其中：

  • n 是文本串 text 的长度
  • m 是模式串 pattern 的长度