Tag Archives: KMP

数据结构重读 – KMP串匹配算法

设:m是模式串pattern的长度,n是主串长度

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

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

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

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

预处理过程:
int get_next(ch[……]

继续阅读