首先明确KMP算法中部分匹配值（ next  数组）的作用： – 在KMP算法中，当主串  S  和模式串  t  匹配过程中出现失配（ S[i]≠t[j] ）时，模式串  t  不需要回退到开头重新匹配，而是根据模式串的部分匹配值（ next  数组）来确定模式串下一次开始比较的位置。 – 部分匹配值  next[j]  的含义是：在模式串  t  中，当  t[j]  与主串失配时，模式串  t  下一次应该从  t[next[j]]  的位置开始与主串继续比较，而主串的比较位置  i  不变（在KMP算法中，主串  i  一般不回溯）。 然后计算模式串  t = ‘abcad’  的部分匹配值  next  数组： –  next  数组的计算方法： –  next[0]= -1 ， next[1]=0 。 – 对于  j > 1 ，设  k = next[j – 1] ，然后比较  t[j – 1]  和  t[k] ： – 如果  t[j – 1] = t[k] ，则  next[j]=k + 1 ； – 如果  t[j – 1]≠t[k] ，则令  k = next[k] ，继续比较，直到  k = -1  或者找到相等的情况。 – 对于模式串  t = ‘abcad’ ： –  next[0]= -1 ， next[1]=0 。 – 计算  next[2] ：因为  next[1]=0 ，比较  t[1]  和  t[0] ， t[1]=’b’ ， t[0]=’a’ ，不相等， next[2]=0 。 – 计算  next[3] ：因为  next[2]=0 ，比较  t[2]  和  t[0] ， t[2]=’c’ ， t[0]=’a’ ，不相等， next[3]=0 。 – 计算  next[4] ：因为  next[3]=0 ，比较  t[3]  和  t[0] ， t[3]=’a’ ， t[0]=’a’ ，相等，所以  next[4]=0 + 1=1 。 最后根据失配情况确定  i  和  j  的值： – 已知第一次出现失配时  i = j = 3 ，根据KMP算法，主串的  i  位置不变（在失配时主串不回溯），所以  i  仍然为  3 。 – 模式串的  j  变为  next[3] ，由前面计算可知  next[3]=0 ，所以  j = 0 。 所以下次开始匹配时， i  的值是  3 ， j  的值是  0 。 故答案为： i = 3 ， j = 0 。

54:03