思维导图（若加载不出来请刷新网页）：
源代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22# 模式匹配算法
## 暴力匹配法
## KMP算法
### 思想
- 跳过中间无用前缀
- 主串不动
### 计算
#### next数组计算
- next数组的每个元素代表主串的前缀与后缀的最长公共子串的长度
- 即：next~i~ = 前i-1的共同前后缀最长公共前后缀的长度 + 1
- 如 ababa的公共最长前后缀时3，则 next[6] = 4
### nextval数组计算
- 在某些情况可能出现缺陷，部分匹配无意义，因此需要计算nextval数组继续优化
- 从j=2开始，判断p~j~是否等于p~next[j]~
- 如果等于则将nextval[j]设置为nextval[next[j]]
- 若不相等则等于next[j]
## 例题如下：
- ```
编号 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
字符 | a | b | a | b | a | a | a |
next | 0 | 1 | 1 | 2 | 3 | 4 | 2 |
val | 0 | 1 | 0 | 1 | 0 | 4 | 2 |
