数据结构（第2版）（C语言实现）课件：串、数组和广义表.pptx

串、数组和广义表;4.1串;4.1串;4.1串;4.1串;4.1串;4.1串;4.1串;4.1串;4.1串;4.1串;4.1串;4.1串;4.1串;4.1串;4.1串;4.1串;4.1串;;4.1串;4.1串;4.1串;4.1串;4.1串;4.1串;4.1串;4.1串;4.1串;4.1串;4.1串;4.1串;4.1串;Brute-Force算法的思想是：从主串S=”s0s1…sn-1”的第pos个字符开始与模式串T=”t0t1…tm-1”的第一个字符比较，如果相等则继续逐个比较后续字符；否则从主串的下一个字符开始重新与模式串T的第一个字符比较，依次类推。如果在主串S中存在与模式串T相等的连续字符序列，则匹配成功，函数返回模式串T中第一个字符在主串S中的位置；否则，函数返回-1表示匹配失败。;4.1串;4.1串;4.1.4KMP算法

KMP算法是由D.E.Knuth、J.H.Morris、V.R.Pratt共同提出的，因此被称为KMP算法（Knuth-Morris-Pratt算法）。KMP算法在Brute-Force算法的基础上有较大改进，可在O(n+m)时间数量级上完成串的模式匹配，主要是消除了主串指针的回退，使算法效率有了很大程度的提高。

1．KMP算法思想

KMP算法的基本思想是：在每一趟匹配过程中出现字符不等时，不需要回退主串的指针，而是利用已经得到前面“部分匹配”的结果，将模式串向右滑动若干个字符后，继续与主串中的当前字符进行比较。;到底向右滑动多少个字符呢？我们先来看一个例子。例如，假设主串S=”abaababaddecab”，子串T=”abad”。KMP算法匹配过程如图所示。KMP算法匹配过程如图所示。;从图中可以看出，KMP算法的匹配次数由原来的6次减少为4次。在第一次匹配的过程中，当i=3、j=3，主串中的字符与子串中的字符不相等，Brute-Force算法从i=1、j=0开始比较。而这种将主串的指针回退的比较是没有必要的，在第一次比较遇到主串与子串中的字符不相等时，有S0=T0=’a’，S1=T1=’b’，S2=T2=’a’，S3≠T3。因为S1=T1且T0≠T1，所以S1≠T0，S1与T0不必比较。又因为S2=T0且T0=T2，有S2=T0，所以从S3与T1开始比较。

。;假设主串S=”s0s1…sn-1”，T=”t0t1…tm-1”。在模式匹配过程中，如果出现字符不匹配的情况，即当Si≠Tj(0≤in,0≤jm)时，有

”si-jsi-j+1…si-1”=”t0t1…tj-1”

??设子串即模式串存在可重叠的真子串，即

”t0t1…tk-1”=”tj-ktj-k+1…tj-1”

也就是说，子串中存在从t0开始到tk-1与从tj-k到tj-1的重叠子串。根据上面两个等式，可以得出：

”si-ksi-k+1…si-1”=”t0t1…tk-1”

如图6.10所示。;如果令next[j]=k，则next[j]表示当模式串中的第j个字符与主串中的对应的字符不相等时，在模式串中需要重新与主串中与该字符进行比较的字符的位置。模式串中的next函数定义如下：;利用next函数值的一个模式匹配例子如图所示。;利用模式串T的next函数值求T在主串S中的第pos个字符之后的位置的KMP算法描述如下。

intKMP_Index(SeqStringS,intpos,SeqStringT,intnext[])

{

inti,j;

i=pos-1;

j=0;

while(iS.lengthjT.length)

{

if(j==-1||S.str[i]==T.str[j])/*如果j=-1或当前字符相等，则继续比较后面的字符*/

{

i++;

j++;

}

else /*如果当前字符不相等，则将模式串向右移动*/

j=next[j]; /*数组next保存next函数值*/

}

if(j=T.length) /*匹配成功，返回子串在主串中的位置*/

returni-T.l