最近在考虑优化一些字符串匹配的方式，但是golang本身有标准库实现，看了下实现，在一定字符长度中会用到RK算法，去搜索了解了下RK算法后，看到kmp的算法，学习实现了一版。
一般判断两个字符串是否相等，是需要每个字符一一比较，最后得出结论相等，复杂度为o(n)。如果需要判断字符是否串包含的关系，暴力的情况会出现比较高的复杂度。而导致出现较多的复杂度的原因，是有个重复比较的过程，下面举例说明一下
例如：
pattern: aaab
text: aaaaaab| a | a | a | a | a | a | b |
|---|---|---|---|---|---|---|
| a | a | a | b |
匹配了三位之后，不等，pattern往后移动一位，继续比较，注意前面说过，比较是需要字符一一进行比对。
| a | a | a | a | a | a | b |
|---|---|---|---|---|---|---|
| a | a | a | b |
不等，重复上面的动作并匹配，直到最后一位确定相等。
| a | a | a | a | a | a | b |
|---|---|---|---|---|---|---|
| a | a | a | a | b |
可以看出暴力的匹配方式，最坏的情况是o(mn)，也很明显可以看到存在重复比较，但是哪些是可以忽略不做比较的呢，为了方便理解前后缀，修改一下pattern和text的示例。
pattern: abcabc
text: abcababcabc| a | b | c | a | b | a | b | c | a | b | c |
|---|---|---|---|---|---|---|---|---|---|---|
| O | O | O | O | O | X | |||||
| a | b | c | a | b | c |
如果往后移动一位继续匹配的话，可以看到
| a | b | c | a | b | a | b | c | a | b | c |
|---|---|---|---|---|---|---|---|---|---|---|
| X | ||||||||||
| a | b | c | a | b | c |
可以看到bcabab对于abcabc压根不可能匹配上，只有在前缀与后缀有相同的情况下，才有机会相等。
| a | b | c | a | b | a | b | c | a | b | c |
|---|---|---|---|---|---|---|---|---|---|---|
| O | O | X | ||||||||
| a | b | c | a | b | c |
也就是移动到上述位置。
不知道上述例子有没有帮助理解前后缀的作用，其实kmp算法主要就是算出前缀表，因为前后缀有相等的，移动位置可以减少不必要匹配，否则就从pattern开始位置开始匹配，下面来尝试求next数组。
对于前后缀表，要求出其对应的前后缀的最长公共子串长度，对于前后缀，例如abc的前缀就是ab，后缀就是bc。h还是相同的pattern例子。
| 子串 | 前缀 | 后缀 | 公共长度 |
|---|---|---|---|
| a | - | - | 0 |
| ab | a | b | 0 |
| abc | ab | bc | 0 |
| abca | abc | bca | 1 |
| abcab | abca | bcab | 2 |
| abcabc | abcab | bcabc | 3 |
所以求出next数组为[0,0,0,1,2,3]
下面来走一遍kmp搜索的流程
pattern: abcabc
text: abcababcabc| a | b | c | a | b | a | b | c | a | b | c |
|---|---|---|---|---|---|---|---|---|---|---|
| O | O | O | O | O | X | |||||
| a | b | c | a | b | c |
i = 5，j = 5,此时匹配错误，j = next[j-1]，也就是 j = next[4]，j = 2| a | b | c | a | b | a | b | c | a | b | c |
|---|---|---|---|---|---|---|---|---|---|---|
| O | O | X | ||||||||
| a | b | c | a | b | c |
i = 5, j = 2,匹配错误，继续，j = next[j-1] = next[1] = 0| a | b | c | a | b | a | b | c | a | b | c |
|---|---|---|---|---|---|---|---|---|---|---|
| O | O | O | O | O | O | |||||
| a | b | c | a | b | c |
可以看到上述流程，即为kmp的整个搜索流程，最坏的情况，也就o(m+n)