详解kmp算法中next数组的求法

详解算法中数组的求法kmp next算法是一种高效的字符串匹配算法，它的核心在于当发生不匹配时，能够KMP利用已经得到的匹配信息，尽可能减少重新匹配的次数算法中有一个关键的KMP辅助数组一一数组下面就来详细解释一下数组的求法next next数组是在已知主串和模式串的情况下，用来描述模式串中每个字符对应的next匹配位置信息的数组数组中的每个元素都表示当模式串中第个字符next next[i]i与主串中对应位置字符不匹配时，模式串应该从哪个位置重新开始匹配这也就是说，数组实际上描述了模式串的“部分匹配”信息next求取数组的具体方法如下next.初始化数组将设为因为当为时，模式串并没有开始匹1next next[O]-1,i配,所以为next[O]-1从开始，遍历模式串，同时记录每个字符的“部分匹配”信息具体来说，

2.i=l就是当模式串的第个字符与主串中对应位置的字符不匹配时，将设i next[i]为这里的含义是，既然前一个字符可以部分匹配主串next[i-l]+l next[iT]+l中的某个字符，那么当前字符就可以从上一个字符的部分匹配结束的位置开始重新匹配如果模式串的第个字符与主串中对应位置的字符匹配，那么将设为

3.i next[i]因为当前字符已经成功匹配了主串中的对应字符，所以不需要重新开始0匹配当遍历完整个模式串后，数组就求出来了

4.next举个例子来说明一下求数组的过程next假设主串为模式串为ABABAC,ABABC初始化数组，将设为

1.next next

[0]-

1.遍历模式串的第个字符因为与主串中的第个字符匹配，所以将21A,A1设为next

[1]Oo.遍历模式串的第个字符因为与主串中的第个字符匹配，所以将32B,B2next设为

[2]Oo.遍历模式串的第个字符因为与主串中的第个字符匹配，所以将43A,A3next遍历模式串的第个字符因为与主串中的第个字符匹配，所以将

5.4B,B4设为设为

[3]Oo next

[4]Oo.遍历模式串的第个字符因为与主串中的第个字符不匹配，所以将65C,C5next设为即

[5]next

[4]+1,

1.遍历模式串的第个字符因为与主串中的第个字符不匹配，所以将76A,A6设为即next

[6]next

[5]+1,

2.遍历模式串的第个字符因为与主串中的第个字符不匹配，所以将87B,B7设为即next

[7]next

[6]+1,

3.遍历模式串的第个字符因为与主串中的第个字符不匹配，所以将98C,C8设为即next

[8]next

[7]+1,4遍历完整个模式串后，数组就求出来了在这个例子中，数组为

10.next next[-1,0,0,0,0,1,2,3,4]o通过以上步骤就可以求出算法中的数组了需要注意的是，求出的KMP nextnext数组要经过一个填充过程，即当模式串长度小于主串长度时，将数组填充为Tnext这样做的目的是为了方便在算法中判断模式串是否已经完全匹配了主串KMP。