首先，非常推薦KMP的講解看這一篇文章：如何更好地理解和掌握 KMP 演算法?
看下兩個版本的代碼，
//next[0] = -1 版本
void getNext(char * p, int * next){
next[0] = -1;
int i = 0, j = -1;
while (i < strlen(p)){
if (j == -1 || p[i] == p[j]){
++i;
++j;
next[i] = j;
} else j = next[j];
}
}
int KMP(char * t, char * p)
{
int i = 0;
int j = 0;
while (i < strlen(t) && j < strlen(p)){
if (j == -1 || t[i] == p[j]){
i++;
j++;
} else j = next[j];
}
if (j == strlen(p))
return i - j;
else
return -1;
}
簡單版本解答：注意到后者的下標為0處的模式碼和匹配碼保存的是其長度，而前者保存的是正常的字符，所以天然的，后者比前者下標大1，也就意味著原來的next陣列要回溯到p位置，現在需要回溯到p+1位置，
next[0] = 0 版本
int TLens = 0,SLens = 0;
void get_nextval(char T[], int next[]){
int i=1, j =1;
next[0] = 0;
TLens = T[0];
while(i < TLens){
if(j == 0 || T[i]==T[j]){
++i;
++j;
next[i] = j;
}
else j = next[j];
}
}
int Index_KMP(char S[], char T[], int pos, int next[]){
SLens = S[0];
int i=1, j=1;
while(i < SLens && j < TLens){
if(j == 0 || S[i] == T[j] ){
++i,++j;
} else j = next[j];
}
if( j == TLens)
return i-j+1;
else return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/230690.html
標籤：其他
上一篇：大學生活日志2.。。。。。