《数据结构与算法》第四章串String概要1.ppt

T j next[j]=k k-1 T j 若pk≠pj,设next[k]=h k-1 next[j+1]=h+1=next[k]+1 T j 若pnext[k] =pj k-1 h-1 j next 1 0 2 1 3 1 4 1 5 1 6 2 7 2 8 3 9 4 10 2 例：T=‘abcdaabcab’ void get_next(SString T,int next[]) { //求模式串T的next函数值并存如数组next j=1; next[j]=0; k=0; while(jT[0]) if(k==0||T[j]==T[k]) {++j; ++k; next[j]=k;} else k=next[k]; }//get_next int Index_KMP(SString S,SString T,int pos) { //利用模式T的 next函数求T在主串S中第pos个字符后的位置 //的 KMP算法，其中T非空， 1≤pos≤StrLength(S) i=pos; j=1; while(i=S[0]j=T[0]) if(j==0 || S[i]==T[j] ) {++i; ++j; } else j=next[j]; if(jT[0]) return i-T[0]; else return 0; }//Index_KMP 由于指针i无须回溯，比较次数仅为n,即使加上计算next[j]时所用的比较次数m，比较总次数也仅为n+m=O(n＋m)，大大快于穷举算法。 a b a c a a c a b c a b a c a b a a a b a c a b 1 2 3 4 5 6 a b a c a b 7 a b a c a b 8 9 10 11 12 a b a c a b 13 a b a c a b 14 15 16 17 18 19 2 1 2 1 1 0 Next b a c a b a P 6 5 4 3 2 1 j a a a a b a a a a a a a a a a b a a a a a b 1 2 3 4 5 6 a a a a a b 5 4 3 2 1 0 Next b a a a a a P 6 5 4 3 2 1 j a a a a a b 7 a a a a a b 8 a a a a a b 9 ......Si-j Si-j+1 Si-j+2 Si-k+2 ... Si-k Si-k+1 ... ... Si p1 p2 pj-k pj-k+1 ... pj-2 pj-1 p1 p2 pk ... pk-2 pk-1 Si-2 Si-1 pj-k+2 pj ≠ || || || || || || || || || || || || 不需要比较 p1 p2 ... pnext[k] ........ 修正next 5 0 0 0 0 0 nextval b a a a a a T 6 5 4 3 2 1 j void get_nextval(SString T,int nextval[]) { //求模式串T的next函数修正值并存如数组nextval j=1; nextval[j]=0; k=0; while(jT[0]) if(k==0||T[j]==T[k]) {++j; ++k; if(T[j]!=T[k]) nextval[j]=k; else nextval[j]=nextval[k]; } else k=nextval[k]; }//get_nextval int index(char s[ ], char t[ ],int pos) { int i, j, k; for(i =pos-1; s[i] != ‘\0’; i++){ for(j=i,k=0;t[k]!=‘\0’s[j]==t[k]; j++,k++); if(t[k] == ‘\0’) return ( i+1); } return ( 0); } * i1+j-1=i2 i1=i2-j+1 i1+1=i2