设：m是模式串pattern的长度，n是主串长度

传统的字符串匹配(暴力法)的时间复杂度是O(n*m)。

而KMP串匹配算法可以将时间复杂度降为O(n+m)，这需要一个额外的预处理O(m)。

KMP优化的地方在于：当出现字符失配的情况时，无需回溯i指针，而是利用已经匹配的部分，将模式串尽可能向右滑动一部分。

实际上：KMP的预处理本身就是一个模式串pattern“自我匹配”的过程。因此，预处理和kmp算法主体非常神似。

预处理过程：
int get_next(ch[......]

继续阅读