以下摘要由GPT-4o生成:
本文讨论了字符串匹配的两种解法：暴力枚举和KMP算法。暴力枚举方法通过双层循环检查每个字符是否匹配，时间复杂度为O(N*M)。而KMP算法则通过构造next数组来优化匹配过程，避免重复比较，从而实现线性时间复杂度O(N+M)。其中，next数组帮助确定在不匹配时回溯的位置，提高了匹配效率。

题目描述

str = abcabca

ptr = abc

那么称 ptr 在 str 字符串中匹配,且第一次匹配位置为 0，第二次为 3；

解法一 暴力枚举;

传统代码处理字符串匹配问题时会进行两次循环，第一层为选定 str 字符串中的字符, 第二层为 开始比较 ptr 与次字符是否相等

  • 如若相等，则比较 str 与 ptr的下一字符，
  • 如若不等，则第一层循环加一，从str 下一个字符开始比较
1
2
3
4
5
6
7
8
9
10
11
12

vector<int> Match(char* str, int n, char* ptr, int m) {
    vector<int> ans;
    for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (str[i + j] != ptr[j]) break;
			if (j == m) ans.push_back(i);//当前位置加入答案数组;
		}
    }
    return ans;
}

**时间复杂度: $O(N *M) $ **

解法二 kmp算法；

而kmp算法的核心是：如若不匹配，则从k = next[k]这个位置开始重新匹配，省去从0开始的中间重复的操作，从而将时间复杂度转换为线性;

关键点：

  • next数组：next[q]表示模式串str[0..q]的最长公共前后缀的长度。
  • 回溯逻辑：当字符不匹配时，通过k = next[k]回溯，利用已计算的信息避免重复匹配。
  • 时间复杂度：O(plen)，每个字符最多被匹配两次（前进和回溯）
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
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 20;
//模式串操作
void cal_next(char *str, int *next, int len){
    int k = -1;//最长公共前后缀长度;
    next[0] = -1;//第一个字符为0；
    for (int q = 1; q <= len - 1; q++) {
        while (k > -1 && str[k + 1] != str[q]) {
            k = next[k];//从最长公共前后缀长度开始;也可以从k--开始，只不过这样更高效;
        }
        if (str[k + 1] == str[q]) {
            k++;
        }
        next[q] = k;//保存最长公共前后缀长度再next数组中
    }
}
int kmp(char* str, int slen, char* ptr, int plen){
    int k = -1;//已匹配字符串数量
    int *next = new int[plen];
    cal_next(ptr, next, plen);
    //遍历主串的每个字符;
    for (int i = 0; i < slen; i++) {
        // 当不匹配且k>-1时，回溯k到前一个位置的next值
        while (k > -1 && ptr[k + 1] != str[i]) {
            k = next[k];
            // 利用next数组跳过已匹配部分
        }
        if (ptr[k + 1] == str[i]) {
            k++;
        }
        // 如果k指向模式串末尾，说明完全匹配
        if (k == plen - 1) {
            // 返回模式串在主串中的起始位置
            return i - plen + 1;
        }
    }
    return -1;
}

int main (){
    char str[20], ptr[20];
    cin >> str >> ptr;
    cout << kmp(str, 10, ptr, 5);
    return 0;
}

**时间复杂度: $O(N + M) $ **