KMP 算法的一些理解

S：目标串
T：模式串

引出问题：

第 1 步：a 和 c不匹配，跳至与模式串头相同的字符。
第 2 步：b 和 c 不匹配，跳至与模式串头相同的字符。
第 3 步：a 和 a 重复匹配。
问题：如何避免重复匹配？（或者说应该回溯到模式串什么位置，这里2到3步j 由 5 回溯到 2 ）

设计算法：

设计一个算法，输入的是模式串不匹配的位置（或模式串回溯前的位置），返回模式串回溯的位置。可以用一个数组表示。如何将回溯前后位置关联起来？

算法特征：

注意观察第 2 步的模式串，c是不匹配位置，c 前面的字符串是 abca，字符串 abca头尾都是 a，这表示 a 已经匹配过，回溯到模式串位置 2 就是了。假设 c 前面的字符串是 abab，应该回溯到模式串位置 3。
因此，回溯前后位置由不匹配位置之前的相同的头切片和尾切片所对应的切片长度决定。
头切片：[0:k-1]
尾切片：[j-k+1:j-1]
切片长度：k-1

一个例子：

j=1, 默认为0
j=2, k-1=0, k=1
j=3, k-1=0, k=1 (c 为不匹配位时，c 之前的字符串是否有相同的头切片和尾切片，对应的切片长度k-1是多少？长度为0)
j=4, k-1=0, k=1 （长度为0)
j=5, k-1=1, k=2（长度为1)

j=6, k-1=1, k=2（长度为1)
j=7, k-1=2, k=3（长度为2)
j=8, k-1=0, k=1（长度为0)
j=9, k-1=0, k=1（长度为0)
j=10, k-1=1, k=2（长度为1)

j=11, k-1=2, k=3（长度为2)
j=12, k-1=3, k=4（长度为3)
j=13, k-1=4, k=5（长度为4)
j=14, k-1=5, k=6（长度为5)
j=15, k-1=6, k=7（长度为6)

j=16, k-1=0, k=1（长度为0)
j=17, k-1=1, k=2（长度为1)

表达式（数组 next）：

KMP算法的优点：

主串不用回溯(只需从头到尾扫描一遍，可以边读边匹配)，模式串不用暴力回溯，优点匹配速度快。

伪代码：