+ T, T4 U. o! m . g) T) N7 }2 C( q五、求next的算法, z; @0 F; k9 a
终于到了最后了~短的串的next值我们可以“看”出来,但长的串就需要借助程序了,具体算法刚接触的时候确实不容易理解,但给我的体验,把上面的内容写完,现在感觉简简单单了…先附上程序再做解释,(终于到了传说中的整整5行代码让我整理了一下午)。: Z6 c+ ]) C! C' F
: o! p) o6 C! r9 p( U( G $ G; b& O( L5 w$ ~0 lint GetNext(char ch[],int cLen,int next[]){//cLen为串ch的长度! K! }5 l9 e+ R% K8 i9 I. m3 G
next[1] = 0; o. Y$ F" n+ c# N4 f9 E g int i = 1,j = 0; $ C6 a7 q6 T! x$ w, |! p while(i<=cLen){ + g, k+ V8 \* _4 T if(j==0||ch==ch[j]) next[++i] = ++j; ' [ E1 R6 |% J( \: e6 O$ I else j = next[j]; 2 w3 V) t; a" P& m g }( p$ C6 Z5 s/ V# K0 n$ O
} 7 J# y3 q+ ~6 P! B- Y+ S5 d! i* @, i$ n- `
还是先由一般再推优化: , Y6 P1 W- o) w8 c' p' D, y直接求next[j+1](至于为什么是j+1,是为了和下面的对应)9 Z T6 p, I2 V8 s' L" a
根据之前的分析,next[j+1]的值为pj+1的前j个元素的收尾重合的最大个数加一。即需要满足两个条件,把它的值一步步“检验”出来。一是“个数最多”的,因此要从可能的最大值开始验;二是“首尾重合”,因此要一一对应验是否相等。1 v2 r8 g/ b) e4 N% T( O
不难理解,next[j+1]的最大值为j,所有我们从next[j+1]=j开始“验证”。有以下优先判断顺序: 4 X) j: R: ]1 @$ ~2 A/ Cif(P1…Pj-1 == P2…Pj) => next[j+1]=j$ F1 K: f1 M. T! h' V1 k
else if(P1…Pj-2 == P3…Pj) =>next[j+1]=j-1 % G# E, ^/ H. I8 L4 r' I8 zelse if(P1…Pj-3 == P4…Pj) =>next[j+1]=j-2& @+ F% t" r' L" [+ y
…, P9 `4 L/ ?& L7 F7 ?* s
… 4 {$ a) X! [2 h…" V, f5 E8 a* V! o2 w' Y
else if(P1P2 == Pj-1Pj) => next[j+1]=3 ( b9 J q: |8 Z9 t7 t( ]else if(P1 == Pj-1) => next[j+1]=2 2 a. e ]4 S0 u4 {" Aelse if(P1 != Pj-1) => next[j+1]=1 ! G) A _0 V2 \) A& c& J! M# G每次前去尾1个,后掐头1个,直至得到next[j+1] 5 W5 u. \5 e0 ^/ Q. t; U . c) K9 ?5 U' \' h9 b" [" b; d# T
再进一步想,next值是一个“工具”,我们单独的求next[j+1]是完全没有意义的,就是说要求next就要把所有j的next求出来。所有一般的,我们都是已知前j个元素的next值,求next[j+1],以此递推下去,求完整的next数组。: {( \+ l$ Q" |8 W1 j3 l1 }3 g
但是,上面的思考过程还是最根本的。所以问题变为两个:知道前j个元素的next的情况下,% ]2 J9 |% {/ f) S' w1 D
①next[j+1]的可能的最大值是多少(即从哪开始验证) # c5 O4 {, ^" q$ B9 ~②某一步验证失败后,需要“前去尾几个,后掐头几个?”(即本次验证失败后,再验证哪个值) 4 r) h# A! V E看一下的分析: " R( O# I8 _: V& _' y% ^6 d- p- [* M+ @# w! e) S/ [
S; ~2 t' U( a/ ?# Z5 L' a
1、next[j+1]的最大值为next[j]+1。 : `' @$ w2 E5 R5 i h! I/ c4 |因为:! r8 h2 Y4 e8 \
假设next[j]=k1,则可以说明P1…Pk1-1=Pj-k1+1…Pj-1,且这是前j个元素最大的首尾重合序列。 + G& g, y# _, B% e如果Pk1=Pj,那么P1…Pk1-1PK=Pj-k1+1…Pj-1Pj,那么k+1这也是前j+1个元素的最大首尾重合序列,也即next[j+1]的值为k1+19 R! E7 N7 d! k; j9 h" _
2、如果Pk1≠Pj,那么next[j+1]可能的次大值为next[next[j]]+1,以此类推即可高效求出next[j+1]* p( a6 t" U- @8 W% u k
这里不好解释,直接看下面的流程分析及图解 + M: ^+ P" W# m : t j# {: ]; i7 t 8 w* j( U# k1 ~开——始——划——重——点! P7 K( x W8 t- r+ A4 r& T6 {3 w
从头走一遍流程/ n' {$ F: H1 }3 C+ P! J5 A
①求next[j+1],设值为m ! ^$ t! G0 T& i- J8 O$ L②已知next[j]=k1,则有P1…Pk1-1 = Pj-k1+1…Pj-19 E( W! w2 x: A5 [! S
③如果Pk1=Pj,则P1…Pk1-1PK = Pj-k1+1…Pj-1Pj,则next[j+1]=k1+1,否则 8 j5 J1 c; c( y c( O④已知next[k1]=k2,则有P1…Pk2-1 = Pk1-k2+1…Pk1-11 [/ I/ D* r$ `1 ]( o( O
⑤第二第三步联合得到: 2 j( c0 g% I# o- F% k# s& Z9 }. X0 e, QP1…Pk2-1 = Pk1-k2+1…Pk1-1 = Pj-k1+1…Pk2-k1+j-1 = Pj-k2+1…Pj-1 即四段重合 $ F0 A5 y$ n; U; F0 K k% d' ^⑥这时候,再判断如果Pk2=Pj,则P1…Pk2-1P~k2 = Pj-k2+1…Pj-1Pj,则next[j+1]=k2+1;否则再取next[k2]=k3…以此类推 $ j. b0 f4 b/ ^* A; H % `* n4 V& S$ `1 X 2 W- H8 |# W# a( x7 B# k上面几步,耐心看下来,结合那个式子很容易看懂。最后,再加一个图的模拟帮助理解: ) v) ]6 \2 J0 G: k# W1 c1、要求next[k+1] 其中k+1=174 e0 }' Z1 ^& H