kmp算法的优化

KMP算法是可以被进一步优化的。
我们以一个例子来说明。譬如我们给的P字符串是“abcdaabcab”，经过KMP算法，应当得到“特征向量”如下表所示： 下标i 0 1 2 3 4 5 6 7 8 9 p(i) a b c d a a b c a b next[i] -1 0 0 0 0 1 1 2 3 1 但是，如果此时发现p(i) == p(k），那么应当将相应的next[i]的值更改为next[k]的值。经过优化后可以得到下面的表格： 下标i 0 1 2 3 4 5 6 7 8 9 p(i) a b c d a a b c a b next[i] -1 0 0 0 0 1 1 2 3 1 优化的next[i] -1 0 0 0 -1 1 0 0 3 0 （1）next[0]= -1 意义：任何串的第一个字符的模式值规定为-1。
（2）next[j]= -1 意义：模式串T中下标为j的字符，如果与首字符
相同，且j的前面的1—k个字符与开头的1—k
个字符不等（或者相等但T[k]==T[j]）（1≤k<j）。
如：T=”abCabCad” 则 next[6]=-1，因T[3]=T[6]
（3）next[j]=k 意义：模式串T中下标为j的字符，如果j的前面k个
字符与开头的k个字符相等，且T[j] != T[k] （1≤k<j）。
即T[0]T[1]T[2]。。。T[k-1]==
T[j-k]T[j-k+1]T[j-k+2]…T[j-1]
且T[j] != T[k].（1≤k<j）;
(4) next[j]=0 意义：除（1）（2）（3）的其他情况。
补充一个next[]生成代码： void getNext(const char*pattern,int next[]){next[0]=-1;int k=-1,j=0;while(pattern[j]!='\0'){while(k!=-1&&pattern[k]!=pattern[j])k=next[k];++j;++k;if(pattern[k]==pattern[j])next[j]=next[k];elsenext[j]=k;}} PROGRAMImpl_KMP;USESCRT;CONSTMAX_STRLEN=255;VARnext:array[1..MAX_STRLEN]ofinteger;str_s,str_t:string;int_i:integer;Procedureget_next(t:string);Varj,k:integer;Beginj:=1;k:=0;whilej<Length(t)dobeginif(k=0)or(t[j]=t[k])thenbeginj:=j+1;k:=k+1;next[j]:=k;endelsek:=next[k];end;End;Functionindex(s:string;t:string):integer;Vari,j:integer;Beginget_next(t);index:=0;i:=1;j:=1;while(i<=Length(s))and(j<=Length(t))dobeginif(j=0)or(s[i]=t[j])thenbegini:=i+1;j:=j+1;endelsej:=next[j];ifj>Length(t)thenindex:=i-Length(t);end;End;BEGINClrScr;{清屏，可不要}Write('s=');Readln(str_s);Write('t=');Readln(str_t);int_i:=index(str_s,str_t);ifint_i<>0thenbeginWriteln('Found''',str_t,'''in''',str_s,'''at',int_i,'.');endelseWriteln('Cannotfind''',str_t,'''in',str_s,'''.');END.index函数用于模式匹配，t是模式串，s是原串。返回模式串的位置，找不到则返回0