前言

数据结构中串模式匹配的C++语言描述实现模板，有详细的步骤解析及使用示例。

代码仓库

暴力/简单/朴素算法

代码模板

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>

//命名空间————————————————————
using namespace std;

//函数声明————————————————————
void useExample();                                      //使用示例
int index(const string &mainStr, const string &subStr); //暴力/简单/朴素算法  返回主串与子串匹配的第一个位置索引

//函数定义————————————————————
//使用示例
void useExample()
{
    const string mainStr = "abcde"; //主串
    const string subStr = "cd";     //子串

    cout << index(mainStr, subStr) << endl; //输出：2

    return;
}

//暴力/简单/朴素算法  返回主串与子串匹配的第一个位置索引
int index(const string &mainStr, const string &subStr) //参数：主串，子串
{
    int i = 0; //主串的匹配位置
    int j = 0; //子串的匹配位置
    // int k = i; //记录每轮匹配时主串和子串匹配的起始位置  用于匹配失败时主串匹配位置的定位回溯

    while (i < mainStr.size() && j < subStr.size()) //遍历主串和子串进行匹配
    {
        if (mainStr[i] == subStr[j]) //匹配成功
        {
            ++i; //继续匹配主串的下一个位置
            ++j; //继续匹配子串的下一个位置
        }
        else //匹配失败
        {
            i = i - j + 1; //主串匹配位置回溯 或：i = ++k;
            j = 0;         //子串匹配位置回溯为0
        }
    }

    if (j == subStr.size()) //遍历完子串，表明匹配成功
    {
        return i - subStr.size(); //返回主串与子串匹配的第一个位置索引  或：return k;
    }
    else //匹配失败
    {
        return -1; //返回-1
    }
}

//主函数————————————————————
int main()
{
    useExample(); //使用示例

    return 0;
}

复杂度

  • 理论时间复杂度：O(n×m)。n为主串规模，m为子串规模
  • 实际（一般情况下的）时间复杂度：：O(n+m)。n为主串规模，m为子串规模
  • 空间复杂度：O(1)。未使用辅助空间

KMP算法

核心思想

  • 作用：字符串（主串和子串）匹配；字符串（主串中的子串间）重复
  • 前缀：除最后一个字符外，字符串的首部连续子串
  • 后缀：除第一个字符外，字符串的尾部连续子串
  • 最长相等前后缀：待匹配字符前的子串中，最长且相等的前后缀子串
  • 前缀表：记录最长相等前后缀的长度
  • next数组：前缀表或值统一减一的前缀表
  • next数组的值next [ j ]：子串的第 j 个字符与主串的当前字符匹配失败，跳转到子串的第next [ j ]个字符与主串的当前字符进行匹配（可能匹配失败或匹配成功）
  • 时间复杂度：O(n+m)。n为主串规模，m为子串/next数组规模
  • 空间复杂度：O(m)。m为子串/next数组规模

代码模板

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
//头文件————————————————————
#include <iostream>
#include <vector>

//命名空间————————————————————
using namespace std;

//函数声明————————————————————
void useExample();                                                                  //使用示例
void getNext(const string &subStr, vector<int> &next);                              //获取next向量：值统一减一/整体右移一位的前缀表
int indexKMP(const string &mainStr, const string &subStr, const vector<int> &next); // KMP算法 返回主串与子串匹配的第一个位置索引

//函数定义————————————————————
//使用示例
void useExample()
{
    const string mainStr = "abcde"; //主串
    const string subStr = "cd";     //子串

    const int subStrSize = subStr.size(); //子串大小

    vector<int> next(subStrSize, -1); // next向量   为子串大小，初始化值-1

    getNext(subStr, next); //获取next向量

    cout << indexKMP(mainStr, subStr, next) << endl; //输出：2

    return;
}

//获取next向量：值统一减一的前缀表
void getNext(const string &subStr, vector<int> &next) //参数：子串，next向量
{
    int i = 0;  //子串中求next值位置的上一位置  主串/后缀的起始位置
    int j = -1; //子串中求next值位置的上上一位置    用于定位：因为需要依据next[j]求next[j+1]    子串/前缀的起始位置

    next[0] = -1; // next向量第一个位置的值必为-1：不存在最长相等前后缀，最长相等前后缀为0，0 - 1 = -1

    while (i < subStr.size() - 1) //遍历子串每个位置   求next值 注意：因为是上一个位置，所以需-1
    {
        // j == -1：j回退到-1，-1 + 1 = 0，最长相等前后缀的长度为0，不存在最长相等前后缀
        //++i：从主串的下一位置匹配
        //++j：j = -1 + 1 = 0，从子串的第一个位置匹配
        // next[i] = j：得next值0：
        //因为不存在最长相等前后缀；含义：若匹配失败，则从子串的第一个位置0进行匹配

        // subStr[i] == subStr[j]：匹配成功
        //++i：继续匹配主串的下一位置
        //++j：继续匹配子串的下一位置
        // next[i] = j：得next值：
        //因为匹配成功；含义：若匹配失败，则从后缀的j位置匹配（因为存在最长相等前后缀，可定位）

        //注意理解：匹配时的i是求next值的位置的上一位置，next[i] = j的++i是求next值的位置

        // else：不存在最长相等前后缀，问题转换：进一步理解为模式匹配问题，递归求next[j]得定位

        if (j == -1 || subStr[i] == subStr[j])
        {
            ++i;
            ++j;

            next[i] = j;
        }
        else
        {
            j = next[j];
        }
    }

    return;
}

// KMP算法  返回主串与子串匹配的第一个位置索引
int indexKMP(const string &mainStr, const string &subStr, const vector<int> &next) //参数：主串，子串，next向量
{
    int i = 0; //主串的匹配位置
    int j = 0; //子串的匹配位置

    const int mainStrSize = mainStr.size(); //主串大小
    const int subStrSize = subStr.size();   //子串大小

    // while (i < mainStr.size() && j < subStr.size()) //遍历主串和子串 输出错误
    while (i < mainStrSize && j < subStrSize) //遍历主串和子串
    {
        // j == -1：子串的匹配位置回溯，匹配主串的下一位置和子串的第一个位置
        // mainStr[i] == subStr[j]：匹配成功，继续匹配主串和子串的下一个位置
        // else：匹配失败，子串的匹配位置依据next向量回溯
        if (j == -1 || mainStr[i] == subStr[j])
        {
            ++i;
            ++j;
        }
        else
        {
            j = next[j];
        }
    }

    if (j == subStr.size()) //遍历完子串，表明匹配成功
    {
        return i - subStr.size(); //返回主串与子串匹配的第一个位置索引
    }
    else //匹配失败
    {
        return -1; //返回-1
    }
}

//主函数————————————————————
int main()
{
    useExample(); //使用示例

    return 0;
}

KMP改进算法

核心思想

  • 解决子串中匹配失败的字符和回溯位置的字符相同导致的冗余匹配问题
  • 时间复杂度：O(n+m)。n为主串规模，m为子串/nextval数组规模
  • 空间复杂度：O(m)。m为子串/nextval数组规模

代码模板

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
//头文件————————————————————
#include <iostream>
#include <vector>

//命名空间————————————————————
using namespace std;

//函数声明————————————————————
void useExample();                                                                     //使用示例
void getNextval(const string &subStr, vector<int> &nextval);                           //获取nextval向量
int indexKMP(const string &mainStr, const string &subStr, const vector<int> &nextval); // KMP算法 返回主串与子串匹配的第一个位置索引

//函数定义————————————————————
//使用示例
void useExample()
{
    const string mainStr = "abcde"; //主串
    const string subStr = "cd";   //子串

    const int subStrSize = subStr.size(); //子串大小

    vector<int> nextval(subStrSize, -1); // nextval向量   为子串大小，初始化值-1

    getNextval(subStr, nextval); //获取nextval向量

    cout << indexKMP(mainStr, subStr, nextval) << endl; //输出：2

    return;
}

//获取nextval向量
void getNextval(const string &subStr, vector<int> &nextval) //参数：子串，nextval向量
{
    int i = 0;  //子串中求nextval值位置的上一位置
    int j = -1; //子串中求nextval值位置的上上一位置   用于定位：因为需要依据nextval[j]求nextval[j+1]

    nextval[0] = -1; // nextval向量第一个位置的值必为-1

    while (i < subStr.size() - 1) //遍历子串每个位置   求nextval值 注意：因为是上一个位置，所以需-1
    {
        // j == -1：不存在最长相等前后缀，j回退到-1
        //++i：从主串的下一位置匹配
        //++j：j = -1 + 1 = 0，从子串的第一个位置匹配
        // nextval[i] = j：得nextval值
        //因为不存在最长相等前后缀，若当前位置匹配失败，则从子串的第一个位置0匹配

        // subStr[i] == subStr[j]：匹配成功
        //++i：继续匹配主串的下一位置
        //++j：继续匹配子串的下一位置

        //改进内容：
        // subStr[i] != subStr[j]：当前位置的字符和回溯位置的字符不同，当前位置的字符匹配失败时不会导致冗余匹配问题
        // nextval[i] = j：得nextval值
        //因为匹配成功，若当前位置匹配失败，则从后缀的j位置匹配（因为存在最长相等前后缀，可定位）
        // nextval[i] = nextval[j]：得nextval值
        //否则当前位置的字符和回溯位置的字符相同，当前位置的字符匹配失败时会导致冗余匹配问题
        //递归获取当前位置的字符和回溯位置的字符不同时的nextval值
        //算法保证正向获取nextval值，反向只需递归一次，当前位置的字符和回溯位置的字符必不同

        //理解：匹配时的i是求nextval值的位置的上一位置，nextval[i] = j的++i是求nextval值的位置

        // else：不存在最长相等前后缀，问题转换：进一步理解为模式匹配问题，递归求nextval[j]得定位

        if (j == -1 || subStr[i] == subStr[j])
        {
            ++i;
            ++j;

            if (subStr[i] != subStr[j])
            {
                nextval[i] = j;
            }
            else
            {
                nextval[i] = nextval[j];
            }
        }
        else
        {
            j = nextval[j];
        }
    }

    return;
}

// KMP算法  返回主串与子串匹配的第一个位置索引
int indexKMP(const string &mainStr, const string &subStr, const vector<int> &nextval) //参数：主串，子串，nextval向量
{
    int i = 0; //主串的匹配位置
    int j = 0; //子串的匹配位置

    const int mainStrSize = mainStr.size(); //主串大小
    const int subStrSize = subStr.size();   //子串大小

    // while (i < mainStr.size() && j < subStr.size()) //遍历主串和子串 输出错误
    while (i < mainStrSize && j < subStrSize) //遍历主串和子串
    {
        // j == -1：子串的匹配位置回溯，匹配主串的下一位置和子串的第一个位置
        // mainStr[i] == subStr[j]：匹配成功，继续匹配主串和子串的下一个位置
        // else：匹配失败，子串的匹配位置依据nextval向量回溯
        if (j == -1 || mainStr[i] == subStr[j])
        {
            ++i;
            ++j;
        }
        else
        {
            j = nextval[j];
        }
    }

    if (j == subStr.size()) //遍历完子串，表明匹配成功
    {
        return i - subStr.size(); //返回主串与子串匹配的第一个位置索引
    }
    else //匹配失败
    {
        return -1; //返回-1
    }
}

//主函数————————————————————
int main()
{
    useExample(); //使用示例

    return 0;
}

总结

不同参考资料中，串模式匹配的描述实现各不相同，但基本思想是一致的。作者使用规范的变量命名、提供详细的步骤解析及使用示例，应用C++语言将其整合成模板，以帮助理解记忆。

参考资料

  • 《2023版数据结构高分笔记》主编：率辉
  • 《2023年计算机组成原理考研复习指导》组编：王道论坛
  • 《大话数据结构》作者：程杰

作者的话

  • 感谢参考资料的作者/博主
  • 作者：夜悊
  • 版权所有，转载请注明出处，谢谢~
  • 如果文章对你有帮助，请点个赞或加个粉丝吧，你的支持就是作者的动力~
  • 文章在描述时有疑惑的地方，请留言，定会一一耐心讨论、解答
  • 文章在认识上有错误的地方, 敬请批评指正
  • 望读者们都能有所收获