KMP finds the position of pattern string P in the main string S.
calculates the next [j] = k function of the pattern string P.
meaning:
is provided with main string S, mode string P, and the first j characters of main string S and mode string P have been completely matched (0roomjmurl, a total of j).
if there is a mismatch on P [j], that is, P [j]! = S [j].
then for the next comparison, just compare P [k] with S [j]. (0 < = k < j, and k makes P [0] ~ P [k] exactly the same as P [j-1murk] ~ P [j-1]).
the algorithm given in the book is:
</span>
(J=2):<br>next:
Active code page: 65001
abababb
--------------------------------
j=2, J_str=ab
k=0, left_str=a, right_str=b
next[2]=0
--------------------------------
j=3, J_str=aba
k=1, left_str=ab, right_str=ba
next[3]=1
--------------------------------
j=4, J_str=abab
k=2, left_str=aba, right_str=bab
next[4]=2
--------------------------------
j=5, J_str=ababa
k=1, left_str=ab, right_str=ba
next[5]=1
--------------------------------
j=6, J_str=ababab
k=2, left_str=aba, right_str=bab
next[6]=2
=================bookNext output==============
bNext[0] = -1
bNext[1] = 0
bNext[2] = 0
bNext[3] = 1
bNext[4] = 2
bNext[5] = 3
bNext[6] = 4
D:\AtomFiles\DataStructCode\KMPstring\Debug\KMPstring.exe ( 8648): 0
...
logically, it seems that bookNext is also wrong.
is it because I don"t understand the KMP algorithm, or is there something wrong in the book?