已知KMP算法中模式串t为“babababaa”，请给出next数组？

Question

已知KMP算法中模式串t为“babababaa”，请给出next数组

Answer 1

abaabcac01122312前两个字母next序列分别为01,直接写上第三个"a" 时，它前一个字母为b,从头开始字母为a, a!=b所以为1第四个"a" 时，前字母为a,从头开始字母为a,a=a,所以值为1＋1=2（相等时为串长加1）第五个"b"，前个字母为a,从头开始a,a=a,为2第六个"c",前个字母为b,再往前是a,ab,从头开始ab串，ab=ab，因此值为2＋1＝3第七个字母为"a",前个字母为c,与从头开始的第一个字母不相等，所以为1第八个为"c",前个字母为a,与开始第一个字母相等，因此为2则返回逻辑“真（TRUE）”，反之返回逻辑“假（FALSE）”。