文档介绍：KMP模式匹配算法
KMP模式匹配算法
KMP模式匹配算法
KＭP算法是一种线性时间复杂度的字符串匹配算法,它是对ＢＦ算法（Bruｔｅ-Forｃe，最基本的字符串匹配算法),需要从字符串s中找出p（首次)出现的位置索引:
BF算法的时间复杂度为Ｏ（strｌen(s）＊sｔrlen（p))，空间复杂度为O(1)；
KMＰ算法的时间复杂度为O（strｌｅn(ｓ）+strｌｅｎ（p）)，空间复杂度为Ｏ（strlen（p)）;
两种算法的主要区别是失配时的处理：假设串s匹配到i位置，串p匹配到j位置:
BF算法中，如果当前字符匹配成功，即s［i+j］==p ［j］，则令j＋+，继续匹配下一个字符;如果匹配失败，即s [ｉ+j]！=ｐ ［ｊ］，则让i+＋并且ｊ＝0，即每次失配时，原串匹配位置向右移动一位(从i+j回溯到i+1）,而j重置为０。
而KＭP算法则是在发生失配时,根据模式中字符和失配在模式中出现的位置，来确定继续进行搜索（ｊ)的位置，而i的位置不会向后回溯.
例如：假定p=’ａbcaｂcaｃab’，令字符串s＝s0s1…sm-1，且假设现在要判断是否存在从 si开始的匹配。
如果si≠a，那么显然可以进行si+1与ａ的比较；
类似地,如果si=a且si+1≠b,那么进行si+1与a的比较；
如果sisi+1=ab且si+2≠c，则出现如下情况：
s=-ab???…?
p='abcaｂcａcａb’
KMP模式匹配算法
KMP模式匹配算法
KMP模式匹配算法
符号？表示不知道ｓ中此处字符是什么,在s中第一个？代表si+2且si+2≠c,因此,搜索的下一步应该是对ｐ的首字符和si++1，因为已经知道si+1与p的第二个字符相同为ｂ，即si+1≠a；
以此类推，假定出现了p前4个字母的匹配,然后失配,即si+4≠b。则出现如下情况:
ｓ＝-abca???…?
p=’abcabcaｃａb’
通过观察可以看到，匹配搜索可以继续把si+4与第二个字符b进行比较。这是在把模式p向右滑动时,发生部分匹配的第一处。因此，通过模式中的字符和失配在模式中出现的位置,就可以确定在模式中继续进行匹配搜索的位置，而不必在ｓ中进行回溯。
为了形式化说明,定义一个模式失配函数：
ﻩ令p=p0p1…pn-1是一个模式,则其失配函数f定义为:
fj=i为满足i<j且使得p0p1…pi=pj-ipj-i+1…pj的最大整数, 如果i≥0-1， 否则
例如: 对于模式p='abcabｃａｃａｂ’，有：
j 0 1 2 ３ 4 5 6 7 8 9
ｐ a b c a ｂ c a c a b
ﻩf －1 —1 －1 0 1 2 3 －1 0 1
根据失配函数的定义，得到如下模式匹配规则：如果出现了形如si-j…si-1=p0p1…pj-1且si≠pj的部分匹配，，若j≠0，则下一趟模式匹配时,从失配字符si和模式串字符pfj-1+1处重新开始比较;若j=０，则继续比较si+1和p0。
按上述匹配规则实现的匹配函数为:
KMP模式匹配算法
KMP模式匹配算法
KMP模