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

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

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

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

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

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

预处理过程:

KMP匹配算法,这里我们和书上的做了一点改进,加入了一个start,即可以支持在主串中查找多次模式串。代码如下:

测试驱动如下:

 

Leave a Reply

Your email address will not be published.