Question

串模式匹配的kmp算法中next[0]的值到底是0还是-1；next[1]的值又到底是1还是0？

上网找了，两种都有，请高手给吹吹这是为何。

Answer 1

因为找next值的时候是从第一个字符开始的，规定第一个字符的next值为0，即如果第一个字符的下标为0则next[0]=0,如果第一个字符的下标是1则next[1]=0。。。因为next值将作为主串的标，数组下标不能为负数，所以next[0]不能为-1。。。

Answer 2

; #include <stdlib.h> #include <vector> using namespace std; inline void NEXT(const string& T,vector<int>& next) } inline string::size_type COUNT_KMP(const string& S, const string& T) else }//while end if(pos==T.size()&&(iter-index)==T.size())++count; } //for end return count; } int main(int argc, char *argv[]) 补上个Pascal的KMP算法源码 PROGRAM Impl_KMP; USES CRT; CONST MAX_STRLEN = 255; VAR next : array [ 1 .. MAX_STRLEN ] of integer; str_s, str_t : string; int_i : integer; Procedure get_nexst( t : string ); Var j, k : integer; Begin j := 1; k := 0; while j < Length(t) do begin if ( k = 0 ) or ( t[j] = t[k] ) then begin j := j + 1; k := k + 1; next[j] := k; end else k := next[k]; end; End; Function index( s : string; t : string ) : integer; Var i, j : integer; Begin get_next(t); index := 0; i := 1; j := 1; while ( i <= Length(s) ) and ( j <= Length(t) ) do begin if ( j = 0 ) or ( s[i]= t[j] ) then begin i := i + 1; j := j + 1; end else j := next[j]; if j > Length(t) then index := i - Length(t); end; End; BEGIN ClrScr; Write(‘s = ’); Readln(str_s); Write(‘t = ’); Readln(str_t); int_i := index( str_s, str_t ); if int_i <> 0 then begin Writeln( 'Found' , str_t,' in ', str_s, 'at ', int_i,' .' ); end else Writeln( 'Cannot find ', str_t,' in' , str_s, '. '); END. index函数用于模式匹配，t是模式串，s是原串。返回模式串的位置，找不到则返回0

Answer 3

next[0] = 0
请参看我的百度空间
http://hi.baidu.com/ozwarld/blog/item/bb81746c39081aed4216941f.html?timeStamp=1304169980484

Answer 4

有两种next函数的求法，next[0]=0和next[1]=1是由一种方法规定的，next[0]=-1和next[1]=0是由另一种方法规定的。这两种方法求出来的失败函数其实是一样的，只不过差了一个1，即：（-1，0）都加1为（0，1）。在程序里用的时候，如果直接拿next[j]来当下标，自然是用上述第一种方法了，用第二种方法求出来的next[j]用的时候得加1。第一种方法有人在csdn上讲了，网页链接，他还讲了怎么求nextval[j]，静心看能看懂。第二种方法比较直观，直接揭示了KMP算法的原理，我老师教学采用的就是这种方法，此处版式受限，以后补我的个人博客链接详细讲解