# KMP算法
[链接1](https://www.ruanyifeng.com/blog/2013/05/)
[链接2](http://jakeboxer.com/blog/2009/12/13/the-knuth-morris-pratt-algorithm-in-my-own-words/)
* proper prefix and proper suffix
以fire举例
fire的
proper prefix有："f", "fi", "fir"
proper suffix有："e", "re", "ire"

* partial match table
          abababca
index:01234567
value:00123401
这里的value = The length of the longest proper prefix in the (sub)pattern that matches proper suffix in the same (sub)pattern.
就是当proper prefix与proper suffix匹配时，最长链的元素个数
![](</document-assets/algorithm-kmp/74da66cc296a192f9c1ee2489d6bb15a5fc91d08923f2aa40ab01cfdc00db707.png>)

跳过元素的个数 = 已经匹配值 - table[已经匹配值 - 1]
partial_match_length - table[partial_match_length - 1]


课本上的方法
考虑四个量:
只看模式串
1. $j = 1,2,3,\dots,n$
2. $T[j]$就是对应$j = n$时模式串的字符
3. $next[j]$:
    $j = 1$时，$next[j] = 0$
    $j = 2$时，$next[j] = 1$
    $j  = 3$开始，假设$j = i(i\geqslant 3)$，那么就看前$i -1$个元素，$next[j]$ = 前缀与后缀部分匹配的最大元素的个数+**1**
4. $nextval[j]$:
    $j = 1$时，$nextval[j] = 0$
    $j = 2$开始，比较$T[j]$和$T[next[j]]$
        * 若相等，则$nextval[j] = nextval[next[j]]$
        * 若不相等，则$nextval[j] = next[j]$