小飞鞋
2018年10月13日
ref: http://www.slyar.com/blog/kmp-next-nextval.html
i 0 1 2 3 4 5 6 7 8
s a b a b a a b a b
next -1 0 0 1 2 3 1 2 3
nextval[0] = -1;
s[1]=b != s[next[1]]=s[0]=a; nextval[1]=next[1]=0;
s[2]=a = s[next[2]]=s[0]=a, nextval[2]=nextval[0]=-1;
s[3]=b = s[next[3]]=s[1]=b, nextval[3]=nextval[1]0;
s[4]=a = s[next[4]]=s[2]=a, nextval[4]=nextval[2]=-1;
s[5]=a != s[next[5]]=s[3]=b, nextval[5]=next[5]=3;
s[6]=b = s[next[6]]=s[1]=b, nextval[6]=nextval[1]=0;
s[7]=a = s[next[7]]=s[2]=a, nextval[7]=nextval[2]=-1;
s[8]=b = s[next[8]]=s[3]=b, nextval[8]=nextval[3]=0;
nextval -1 0 -1 0 -1 3 0 -1 0
有的时候下标从1开始即 0 1 0 1 0 4 1 0 1
0
0