文档介绍：精品范文模板 可修改删除
免责声明：图文来源于网络搜集，版权归原作者所以
若侵犯了您的合法权益，请作者与本上传人联系，我们将及时更正删除。
撰写人：___________日 期：___________
p0p1p2≠p1p2 p3。所以满足条件的k不存在，即f(3)=-1。
当j=4时，k可能的取值为0,1,2,3。由于p0=p4，p0p1≠p3 p4，p0p1 p2≠p2 p3 p4且p0p1 p2 p3≠p1p2 p3 p4。所以满足条件的k为0，此时f(4)=0。
当j=5时，k可能的取值为0,1,2,3,4。由于p0≠p5，p0p1= p4p5，p0p1p2
≠p3 p4 p5，p0p1 p2 p3≠p2 p3 p4 p5且p0p1 p2 p3 p4≠p1p2 p3 p4 p5，所以f(5)=1;
同理可求当j=6时，f(6)=-1。
求完模式串p的失效函数后，就可以应用KMP算法对它进行匹配。具体的匹配过程分为两种情况。假设在进行某一轮比较时，失配的情况发生在模式
精品范文模板 可修改删除
免责声明：图文来源于网络搜集，版权归原作者所以
若侵犯了您的合法权益，请作者与本上传人联系，我们将及时更正删除。
p的第j位，那么如果j=0，则让目标的指针前进一位，模式串的起始比较地址 回到P0处。否则，在进行下一轮的比较时，目标指针不发生回溯，仍指向失配的位置，而模式串的起始比较地址为Pf(j-1)+，函数f(j)仅与字符串P有关，而与目标串无关。所以只需给定模式字符串P，无论目标字符串T的取值是什么，均可应用同一个失配函数对它匹配。
例子
模式串P=”caatcat”,目标串T=”ctcaatcacaatcat”。
第一次比较：
T c t c a a t c a c a a t c a t
P c a a t c a t
第二轮比较：
T c t c a a t c a c a a t c a t
P c a a t c a t
第三轮比较：
T c t c a a t c a c a a t c a t
P c a a t c a t
第四轮比较：
T c t c a a t c a c a a t c a t
P c a a t c a t
第一轮比较，模式串与目标串在第二个字符处发生匹配 。算法检测到失陪后结束本轮比较，并且指针不发生回溯，仍指向失配位置。由于失配发生在第二个字符处，此时
精品范文模板 可修改删除
免责声明：图文来源于网络搜集，版权归原作者所以
若侵犯了您的合法权益，请作者与本上传人联系，我们将及时更正删除。
j=1，所以模式匹配P在下一轮匹配时的起始比较地址是P f(1-1)+1，即p0。
第二轮比较中，由于模式字符串P所在的第一个字符处发生失配，此时j=0，所以让目标的指针前进一位，模式的其实比较位置回到p0。
接着进行第三轮比较。