湖南涉外经济学院
教案
学院信息科学与工程学院
系/教研室软件工程系
课程名称数据结构
主讲教师邹竞
湖南涉外经济学院
教案
教案
教案
教案
教案
教案
教案
教案
教案
教案
j 1 2 3 4 5 6
模式串 a b a a b c
next[j]0 1 1 2 2 3
3．如何求next[ ]函数
已知next[1] = 0，假设next[j] = k且tj = tk，则有next[j+1] = k+1= next[j]+1；
若next[j] = k且tj ≠ tk，则需往前回溯，检查tj = t?。

这实际上也是一个匹配的过程，不同在于主串和模式串是同一个串。

若k’=next[k]且tj = tk’，则next[j]=next[k]+1，若tj ≠ tk’ 则继续往前回溯，直到存在k’’使tj = tk’’或k’’=0
j12345678
模式串b a b b a b a b
0 1 1 2 2 3 4 3
利用KMP算法的子串定位函数
int IndexKMP(STRING *S,*T)
{∥利用模式串T的next函数,求T在主串S中的位置
∥的KMP算法。

其中T非空
i=0; j=1;
while(i<S->length && j<=T->length)
if(j==0 || S->str[i]==T->str[j-1])
{ ++i; ++j；} ∥继续比较后继字符
else j=next[j]; ∥模式串向右移动
if(j>T->length)
return i-T->length+1; ∥匹配成功
else return 0;
}∥IndexKMP
如何求next函数：
已知next[1]=0，
假设next[j]=k且pj=pk，
则有next[j+1]=k+1=next[j]+1；
若next[j]=k且pj≠pk，则需往前回溯，检查pj=p?。

这实际上也是一个匹配的过程，不同在于主串和模式串是同一个串。

若k’=next[k]且pj=pk’，
教案
维的长度，
教案
教案。