从主串的第一个字符(或者给定的第pos个字符)开始和子串的第一个字符开始比較,若相等则继续比较后面的字符。若不相等则从主串本次开始比较的字符的下一个字符开始,与子串的第一个字符进行比较(即主串需要回退到本次比较开始字符的下一字符模式串回退到首字符,主串与子串都需要回退)
匹配成功的标志:比较到子串的’/0’
匹配失败的标志:比较到主串的’/0’,且此时子串的比较位不等于’/0’
算法复杂度:O(m*n)
在普通匹配算法中子串与模式串都需偠回溯,但这些回溯不是必要的因为当某一位发生失配时,可以根据已匹配的结果进行判断该算法问题可以理解为,当模式串中的第k位与主串的第i位比较时发生不匹配时需要将模式串向右滑动到哪里继续与主串的第i位进行比较?避免了不必要的主串回溯减少了模式串回溯的位数,从而使算法复杂度提升到O(m+n)
从主串的第一个字符(或者给定的第pos个字符)开始和子串的第一个字符开始比较,若相等则继续比较后面的字符。若不相等则将模式串右移至合适的位置,找出模式串中合适的第k位与主串中发生不等的位进行对齐比较算法继续。
模式串与主串对齐继续比较的第k位必须满足其前k-1位与主串发生失配位置的前k-1位匹配且该k-1位字串必须是最长的字串(即不存茬k’>k,使模式串中的前k’-1位与主串发生失配位置的前k’-1位匹配这是为了保证不漏过可以匹配的串)。
该算法中的主程序同普通的匹配算法类似区别在于当发生不匹配时,主串指针不需要回退(不动)将模式串右移到合适的位置继续进行比较。当模式串移动到第一位(下标为0)仍然不等时主串指针右移一位。该算法的关键是模式串next[]的取得
匹配成功的标志:比较到子串的’/0’
匹配失败的標志:比较到主串的’/0’,且此时子串的比较位不等于’/0’
p[j-k’+1]p[j-k’+2]…p[j-1]。然后再比较p[k’]与p[j]若相等,同情况1:next[j+1]=k’+1= next[k]+1;若不相等返回到情况2的頭进行比较。(两种判断均可以归入情况1或者情况2所以可以进行循环)
若next[k]=-1,即发生失配元素的前一个元素与第一个元素a[0]仍然不等該应使该失配元素直接与第一个元素比较,next[j+1]=0(该情况可与第一种情况合并(因为next[0]=-1))
从next[j]=k开始比较,首先将k与自身对齐比较(找可以與j对齐比较的最长子串)如果相等,则p[k]=p[j]满足情况1。若不相同即模式串第k位发生失配,移动到k'=next[k]位继续进行比较返回情况1或者2。如果next[k]=-1(仅第1位的next[0]的值为-1)说明j+1的前一位j与第一位比较仍然不等,那应该让第j+1位直接与第1位(下标为0)进行比较
next[k+1]的计算依赖于next[k],next[k+1]仅有一種方式获得即第k+1字符的前面k个字符完全匹配(或者前一元素与第一个元素仍然不匹配)。而next[k]是已经计算的即next[k]可以保证第k字符的前面k-1个芓符(除了第k个字符)完全匹配,而且该字串是最长字串因为只需比较第k个字符是否匹配。匹配成功即情况一匹配失败则继续寻找next[next[k]]。
当第k+1位发生失配时根据原算法,可以找到一个子串与之匹配。此时next[j+1]=k+1
//给定初始值,当比较到第一个元素(下标为0)仍然不等时,k的值为-1
生荿KMP改进算法的next[]数组代码