在字符串的KMP模式匹配算法中，需先求解模式串的next函数值，其定义如下式所示，j表示模式串中字符的序号（从1开始）。若模式串p为“abaac”，则其next函数值为（ ）。
- A.01234
- B.01122
- C.01211
- D.01111
正确答案及解析
正确答案
解析
＜k＜k＜k＜j的数k，由（3）式，next[2]=1；
＜k＜j的数k=2，同时需要满足'p1p2lpk-1'="pj-k+1pj-k+2Lpj-1"。
＜k＜j的数k=2或3：
＜k＜j的数k=2、3或4：
本题考查字符串的模式匹配运算知识。
KMP是进行字符串模式匹配运算效率较高的算法。根据对next函数的定义，模式串前两个字符的next值为0、1。对于第3个字符“a”，其在模式串中的前缀为“ab”，从该子串找不出前缀和后缀相同的部分，因此，根据定义，该位置字符的next值为1。
对于第4个字符“a”，其在模式串中的前缀为“aba”，该子串只有长度为1的前缀“a”和后缀“a”相同，根据定义，该位置字符的next值为2。
对于第5个字符“a”，其在模式串中的前缀为“abaa0”，该子串只有长度为1的前缀“a”和后缀“a”相同，根据定义，该位置字符的next值为2。
综上可得，模式串“abaac”的next函数值为01122。
一、对于公式：
1、由（1）式，当j=1时，next[1]=0；
2、当j=1时，由（2）式，max{k|1＜k＜k3、取值范围，j、k都为正整数，且1＜=j＜=5
【可根据下面的具体过程理解公式】
二、本题计算如下：
1、j=1，由（1）式，next[1]=0；
2、j=2，找不到满足1＜k＜j的数k，由（3）式，next[2]=1；
3、j=3，满足1＜k＜j的数k=2，同时需要满足'p1p2lpk-1'="pj-k+1pj-k+2Lpj-1"。
'p1p2Lpk-1'='p1p2Lp1'=p1，为第一个字母a；'pj-k+1pj-k+2Lpj-1'='p2p3Lp2'=p2，为第二个字母b，a!=b，此时，找不到k不满足条件，由（3）式，next[3]=1。
4、j=4，满足1＜k＜j的数k=2或3：
（1）当k=2，'p1p2Lpk-1'='p1p2Lp1'=p1，为第一个字母a，'pj-k+1pj-k+2Lpj-1'='p3p4Lp3'=p3，为第三个字母a，满足'p1p2Lpk-1'='pj-k+1pj-k+2Lpj-1'。
（2）当k=3，'p1p2Lpk-1'='p1p2Lp2'=p1p2，为第一二字母ab，'pj-k+1pj-k+2Lpj-1'='p2p3Lp3'=p2p3，为第二三个字母ba，不满足'p1p2Lpk-1'='pj-k+1pj-k+2Lpj-1'。
综上可得，当j=4时，满足条件的最大k值为2，next[4]=2。
5、j=5，满足1＜k＜j的数k=2、3或4：
（1）当k=2，'p1p2Lpk-1'='p1p2Lp1'=p1，为第一个字母a，'pj-k+1pj-k+2Lpj-1'='p4p5Lp4'=p4，为第四个字母a，满足'p1p2Lpk-1'='pj-k+1pj-k+2Lpj-1'。
（2）当k=3，'p1p2Lpk-1'='p1p2Lp2'=p1p2，为第一二字母ab，'pj-k+1pj-k+2Lpj-1'='p3p4Lp4'=p3p4，为第三四个字母aa，不满足'p1p2Lpk-1'='pj-k+1pj-k+2Lpj-1'。
（3）当k=4，'p1p2Lpk-1'='p1p2Lp3'=p1p2p3，为第一二三字母aba，'pj-k+1pj-k+2Lpj-1'='p2p3Lp4'=p2p3p4，为第二三四个字母baa，不满足'p1p2Lpk-1'='pj-k+1pj-k+2Lpj-1'。
综上可得，当j=5时，满足条件的最大k值为2，next[5]=2。
根据上面的分析过程，可以得出next[]函数值为01122。
