10.8

对kmp算法进行了学习,其中重点学习了next【】和nextval【】的计算方式,

其中next算法的代码实现如下:

void get_next(SString T, int &next[]) {

i= 1;

next[1] = 0;

j = 0;

while( i<T[0]){

if(j==0 || T[i] == T[j]){

++i;

++j;

next[i] = j;

} else

j = next[j];

}

}

其中nextval算法实现如下:

void get_nextval(SString &T, int &nextval[]) {

i = 1;

nextval[1] = 0;

j = 0;

while (i < T[0]) {

if (j = 0 || T[i] == T[j]) {

++i;

++j;

if (T[i] != T[j]) nextval[i] = j;

else nextval[i] = nextval[j];

}

else j = nextval[j];

}

}

用语言描述,next就是第j个字符前的字符串和串前端的字符串有相同的最大字符数加一,如abaabb

其中第6个字符b前ab和前端的ab是相同的最大字符数为2,所以2+1=3就是第六个字符的next。

而nextval模式的第i位的nextvalue值:如果该位与它next值只向的位相同,则nextvalue[i]=next[next[i]]

如果不同,nextvalue[i]=next[i]

上一篇:KMP算法以及优化(代码分析以及求解next数组和nextval数组)


下一篇:串的基本算法理解