赵文华

（转帖）KMP算法中的 Next 求解方法  s. |, C) T0 v* k
！！向作者zmrbak 致敬9 L  H5 J9 U) O

% I' Q' d6 K; }4 \! iKMP的NEXT数组的求法
# ~; {  Y4 x% m2 M" O
( N6 U/ i7 X: X2 ~) s. j
& C& ]$ W2 m6 V, h. [: i7 T& \串 ‘ababaaababaa’ 的next数组为（  ）。【中山大学 1999 一、7】
. W+ T2 x# k) o3 yA.012345678999 B.012121111212 C.011234223456  D.0123012322345
" j1 U- t9 L1 W. \7 e4 W0 |6 da        b        a        b        a        a        a        b        a        b          a           a
$ m+ i5 Y; u* j7 |* I1        2        3        4        5        6        7        8        9        10        11        127 r9 Z  X) c7 M9 a/ \  h; J3 {
现在我们直接求NEXT数组中的第10位
* c4 R+ h2 ~, Z2 _6 \j=10;
0 G% q5 J* Q7 ?9 w6 S0 l6 k4 l根据定义要求:
& j/ z& D- _& Q/ Y8 A' n! |        1<k<j4 Y: A0 v# |7 r
那么k值最大只能取j-1=10-1=9了。
2 O( O/ }/ ~: i2 r$ z2 U/ bP1P2….Pk-1 字符串就是‘P1P2….P8’
. l6 L# m  m0 U( |) C8 BPj-k+1…Pj-1字符串就是‘P2P3……P9’
& r& }0 V& G6 e. k( u参考上表，实际上就变成了下表字符串的比较:
2 \2 B9 X8 b* K( YK值                      1        2        3        4        5        6        7        8& x) Z( g# h  z8 r' N7 g" p' S# s
( F$ F, f9 t" q# L. o, |8 K5 w
                             2        3        4        5        6        7        8        9  G/ F5 @# C) _
        匹配结果
% S5 B/ P2 o$ k  o* d7 d9                           a        b        a        b        a        a        a        b
! P: e) t/ u+ Q$ w                             b        a        b        a        a        a        b        a1 A) _  h, C$ o0 I( _" q7 B
           X. O$ }5 z) P8 z  X
8                           a        b        a        b        a        a        a        
2 N) u* s6 Y; \7 b. U                             a        b        a        a        a        b        a
0 ]* P3 w# l; M9 H- y7 D" n           X) I* G6 n4 ^; R3 \$ X5 K
7                          a        b        a        b        a        a                - E7 r- T" M0 P* ]/ }
                             b        a        a        a        b        a6 D; \) @. ]5 }* `1 w8 P- J
           X
0 L$ e+ u5 ^0 \& A  y9 Q6                          a        b        a        b        a                        ' F# e6 U# V3 s
                            a        a        a        b        a1 E" z5 G# J% n, X6 H4 I9 G
           X& Q, _' \7 g8 o, Q% s
5                         a        b        a        b                                9 I  T3 A2 p2 s$ J. t6 \% z. ^  E
                           a        a        b        a4 B7 z& F" [3 ?
           X
* ~* ^8 E$ W3 M$ v4                         a        b        a                                        1 G( ?! J5 o! @& K+ K2 {. a
                           a        b        a
* i" ?1 I. b" Y           OK8 {# U# Y. o# T  Y8 J
3                         a                                                        ' i7 i. N0 z; J" u
                 b        a
6 U, f! R. `7 e0 i+ G5 P        无需比较
0 T. {, B1 D! j3 `) ]- u0 f如上图示，很快“计算出”NEXT数组中第十的数字为“4”。其他位置的值可以按照上面的方法处理。