KMP算法入门

KMP解决的是模式串S

S和文本串T

T之间的匹配问题。传统和暴力算法，在复杂度方面不够优秀，根本原因在于对模式串没有的规律没有加以利用，导致进行了多余的匹配。而KMP算法的关键也在于next

next数组，求解出了模式串next

next数组，也就求解出来了对于当前模式串在某一位置失配后，接下来去哪一位置进行匹配的问题。有了这个从而提高在匹配过程中的效率。

next数组的求解

对文本串和模式串进行如下的规定：

|S|=n,|T|=m,S=s

s

1

…s

n−1

,T=t

t

1

…t

m−1

|S|=n,|T|=m,S=s0s1…sn−1,T=t0t1…tm−1

对next

next数组的理解，可以为：如果当前在模式串S

S中的某一位置x

x发生失配，即在主串T

T中某一可能的位置y

y,如果有s

x

≠t

y

sx≠ty，对于模式串来说，应该用其的哪个字符接着和s

x

sx 进行比较。

从上述描述中，不难发现，对于主串的指针，在失配的时候是不回退的。而在传统的暴力求解算法上，如果发生了失配，主串的指针是要回退到模式串头部对应主串的位置+1的位置上，这样的回退，显然效率很低。从这个角度上来看，也说明了KMP有很好的效率。

next数组的含义

next

next数组的含义已经说过，其更本质的含义是，对于模式串的某一位置x

x，s

s

1

…s

x−1

s0s1…sx−1的前缀和后缀相同的最大长度。这样说还不够具体，用一个实例来描述一下。

假设有模式串S=ababaca

S=ababaca

x

x串最长前缀和最长后缀相同的串最长长度next

next值0a

anull

null0-11ab

abnull

null0-12aba

abaa

a103abab

ababab

ab214ababa

ababaaba

aba325ababac

ababacnull

null0-16ababaca

ababacaa

a10

解释一下上表，如当x=6

x=6时，模式串最后发生了失配，也就是最后的a

a和文本串不匹配，在保证主串指针不回退的情况下，那么主串该和模式串的哪个字符来比较了，显然是第0个字符，也就是开头的a

a.

再比如，当x=4

x=4的时候发生失配，那么下面就是主串的模式串的第2个字符进行比较。

next数组求解代码

void getnext(){

int len = strlen(str),k = -1;

nxt[0] = -1;

for(int i = 1;i<=len-1;++i){

while(k>-1&&str[k+1]!=str[i]) k = nxt[k];

if(str[k+1] == str[i]) k++;

nxt[i] = k;

}

}