发布网友 发布时间:2022-04-27 09:22
共4个回答
热心网友 时间:2023-09-18 12:18
因为找next值的时候是从第一个字符开始的,规定第一个字符的next值为0,即如果第一个字符的下标为0则next[0]=0,如果第一个字符的下标是1则next[1]=0。。。因为next值将作为主串的标,数组下标不能为负数,所以next[0]不能为-1。。。热心网友 时间:2023-09-18 12:18
; #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; Procere 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热心网友 时间:2023-09-18 12:19
next[0] = 0参考资料:http://hi.baidu.com/ozwarld/blog/item/bb81746c39081aed4216941f.html?timeStamp=1304169980484
热心网友 时间:2023-09-18 12:19
有两种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算法的原理,我老师教学采用的就是这种方法,此处版式受限,以后补我的个人博客链接详细讲解