1
KM
P
算
法
KMP
算
法
，
全
称
Knuth-Morris-Pratt
字
符
串
搜
索
算
法
，
是
⼀
种
线
性
时
间
复
杂
度
的
字
符
串
匹
配
算
法
。
它
的
主
要
思
想
是
在
发
⽣
不
匹
配
时
，
能
知
道部
分
已
经
匹
配
的
字
符
序
列
的
后
缀
和
模
式
串
的
前
缀
存
在
重
复
，
因
此
可
以
利
⽤
这
些信
息
避
免
重
新
⽐
较这
些
字
符
。
KMP
算
法
的
核
⼼
在
于
构
建
⼀个
名
为
“
Next
数
组
”
的
辅
助
数
组
，
该
数
组
⽤
于
存
储
模
式
串中
每
个
位
置
前
的
⼦
串
的
最
⻓
相
同
前
后
缀
的
⻓
度
。
当
主串中
的
字
符
与
模
式
串
的
字
符
不
匹
配
时
，
可
以
根
据
Next
数
组
的
值
，
快
速
将
模
式
串
滑
动到
正
确的
位
置
，
从
⽽
避
免
不
必
要
的
⽐
较
。
1.
Next[0] = -1
（
或
0
，
视
具
体
实
现
⽽
定
，
表
示空
字
符
串
没
有
前
后
缀
）
2.
Next[1] = 0
（
单
个
字
符
的
字
符
串
没
有
前
后
缀
）
3.
对
于
i > 1
，
Next[i]
的
计
算
依
赖
于之
前
的
Next
值
。
假
设
已
经
求
出
了
Next[1]
到
Next[i-1]
，
现
在
要
求
Next[i]
。
我
们
需
要
找
到
⼀个
最
⼤
的
k
（
k < i
），
使
得
模
式
串
的
以
k
结
尾
的
⼦
串
与
以
i
结
尾
的
⼦
串
的
前
缀
相
同
。
如
果
模
式
串
的
第
i
个
字
符
与
第
Next[j]
个
字
符
相
同
（
其
中
j = Next[i-1]
），
则
Next[i] = Next[j] + 1
；
否
则
，
我
们
需
要
继续
检
查
Next[Next[j]]
，
直
到
找
到
匹
配
或
到
达
Next[0]
。
1.
初
始
化
两个
指
针
，
i
指
向
主串
的
起
始
位
置
，
j
指
向
模
式
串
的
起
始
位
置
。
2.
逐
个
⽐
较
主串
和
模
式
串
的
字
符
，
如
果
相
同
则
继续
⽐
较
下⼀个
字
符
；
如
果
不
同
，
则
根
据
Next
数
组
的
值
将
模
式
串
向右
滑
动
，
j
的
值
更
新
为
Next[j]
。
3.
重
复
上
述
步
骤
，
直
到
j
达
到
模
式
串
的
⻓
度
，
表
示
找
到
匹
配
；
或
者
i
达
到
主串
的
末
尾
，
表
示
未
找
到
匹
配
。
⼀
、
算
法
原
理
Next
数
组
的
构
建
⼆
、
匹
配过
程
