kmp算法是一种字符串按位匹配失效时的处理办法。
字符串在匹配时难免会出现部分匹配的情况，当某一位不匹配时，顺其自然的理解就是子串找错位置了，子串不在这儿（即开始的地方就出错了，尽管之前的所有位置都匹配成功）。直接的处理办法就是母串开始位置向后移动一位，子串从头开始继续找。这就是简单粗暴的匹配失效处理办法。
简单粗暴的处理方法中有很强的无力感，即我承认子串不在这，但是前面也确确实实匹配到了一部分，没必要完全否定从头开始吧。所以kmp出现了，kmp通过next数据记录了已经匹配的部分字符串中可以利用的信息，或者说通过计算next数组我们可以没必要彻底否定过去。理解kmp算法的关键也就是理解next数组。next数组表示匹配失效时子串需要重新开始匹配的位置（next数组的意义）。
首先next为子串所有，且与子串长度相同。next数组中每一位的值表示子串中该位置之前且不包括该位置的字符串的最长相同前后缀的长度（next数组的计算方法）。分三步理解：1、next数组每一位的值表示一个长度；2、它是最长相同前后缀的长度；3、它是子串中该位置之前且不包括该位置的字符串的最长相同前后缀的长度。
其实到这就说清楚了next是什么，非要多说一点的话，我认为需要理解什么是最长前后缀。字符串的前缀表示该字符串的一个切片，该切片以字符串的首字母开头，任意非尾字母结尾。例：'ABCD'的前缀为‘A’,'AB','ABC'.同理后后缀也是字符串的一个切片，该切片以任意非首字母开头，以字符串的尾字母结尾。例：‘ABCD’的后缀为‘D’,'CD',BCD'。
前面说next数组记录了已经匹配的字符串中可以利用的信息。next表示最长相同前后缀，言外之意就是首尾相同的最大长度。因为只有当匹配失效时才会启用next数组，所以可以认为失效之前的子串在母串中已经全部找到（二者是相同的）即next数组记录了子串首部与母串尾部（理解为已经匹配的尾部）相同的长度，根据next我们完成了把子串的头与母串的尾（同样是已经匹配的尾部）对齐的操作。成功利用了已匹配的信息。
讲完了，kmp就是这样一个根据已经匹配的子串最长前后缀的长度决定当前匹配失效时重新开始匹配的位置的方法。
网友评论