数据结构篇_编程思想板块_第四章串的模式匹配

• 编程思想板块最主要的内容是数据结构经典题目及解答题目所需的编程思想，愿对您能有所帮助

四、串的模式匹配

1）朴素模式匹配算法（暴力算法）

1. 主串称目标串，子串称模式串

2. 算法思想：逐个比对字符

3. 无论链式/顺序：最坏时间复杂度为：O(mn) (n，m分别是主串和模式串长度)

​ 最好时间复杂度：O(n)(即每次比对都在第一个字符处失败)

​ 最坏比较字符总次数：m*（n-m＋1）

2）KMP算法

1. 算法思想：算出PM表然后依据此表移动模式串和模式串指针的位置

2. 子串右移位数 = 已匹配的字符数 - 对应的部分匹配值

3. 需注意的点：

①　PM表会右移一位（第一个元素右移后空缺用-1填充）使之用next[j]就可以取到子串指针j将要指向的位置

②　next数组计算看王道串的课后习题

③　为了让公式更简洁，如果串的位序是从1开始的，则next数组才需要整体加1，若是从0开始的则不用

④　next[j]的含义：在发生失配时，子串指针跳到子串的next[j]位置重新与主串当前位置进行比较（主串指针回溯-KMP优点）

⑤　时间复杂度：O(m+n);

求next数组：O(m)

⑥　

(1) ：

1. KMP算法进一步优化：如果出现了（P为子串)时，用next数组中符合此条件的从左至右把前面的字符的next值赋给后一个