type
status
password
date
slug
summary
category
URL
tags
icon
简介
KMP算法是一种改进的字符串匹配算法。KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。下面示例，在字符串
A="ababababca"中查找字符串B="abababca"。PMT表
KMP算法的核心，是一个被称为部分匹配表(Partial Match Table)的数组。对于要查找的字符串
B="abababca"，它的PMT表格如下：char: | a | b | a | b | a | b | c | a |
index： | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
value: | 0 | 0 | 1 | 2 | 3 | 4 | 0 | 1 |
next： | -1 | 0 | 0 | 1 | 2 | 3 | 4 | 0 |
通过PMT表格可以求得next数组。
next数组中存储了当主串与模式串的某一位字符不匹配时，模式串要回退的位置。KMP算法需要每次使用next数组来移动模式串。next[j]=前面j-1位字符串的最大前后缀重合字符数加1。- 前缀：包含首位字符，但不包括末尾字符的字符串。
- 后缀：包括末尾字符，但不包括首位字符的子串。
例如：字符串”ababa”，它的前缀集合为{”a”, ”ab”, ”aba”, ”abab”}，它的后缀集合为{”baba”, ”aba”, ”ba”, ”a”}， 两个集合的交集为{”a”, ”aba”}，其中最长的元素为”aba”，长度为3。
next数组是value数组向右移动一位。PMT使用
如下图所示，在字符串ABABABABCA中寻找ABABABC，在图中红色的部分发现失配。失配位置对应PMT表的next数组是4，所以将index=4的地方对准上表，并重新比较。
28. 实现 strStr() - 重点next数组的计算方式
