2023年7月20日发(作者：)

顺序表⽰的串——串的模式匹配1——基本内容串的模式匹配也称为⼦串的定位操作，即查找⼦串在主串中出现的位置。它是经常⽤到的⼀个算法，也是数据结构中的⼀个难点之⼀。串的模式匹配算法常见的有两种：Brute-Force朴素模式匹配算法和KMP算法。【Brute-Force算法】⼦串的定位操作串通常称为模式匹配，是各种串处理系统中最重要的操作之⼀。设有主串S和⼦串T，如果在主串S中找到⼀个与⼦串T相等的串，则返回T的第⼀个字符在串S中的位置。其中，主串S⼜称为⽬标串，⼦串T⼜称为模式串。Brute-Force算法的思想是：从主串S=“sn-1”的第pos个字符开始与模式串T=“-1”的第⼀个字符进⾏⽐较，如果相等则继续逐个⽐较后续字符；否则从主串的下⼀个字符开始重新与模式串T的第⼀个字符进⾏⽐较，依此类推。如果在主串S中存在与模式串T相等的连续字符序列，则匹配成功，函数返回模式串T中第⼀个字符在主串S中的位置；否则返回-1表⽰匹配失败。假设主串S="ababcabcacbab"模式串T="abcac",S的长度n=13,T的长度m=5。⽤变量i表⽰主串S当前正在⽐较字符的下标，变量j表⽰⼦串T中当前正在⽐较字符的下标。模式匹配的过程如图【BMP算法】KMP算法是由、、共同提出的，因此被称为KMP算法（Knuth-Morris-Pratt算法）。KMP算法在Brute-Force算法的基础上有较⼤的改进，可在O(n+m)时间数量级上完成串的模式匹配，主要是消除了主串指针的回退，使算法效率有了很⼤的程度的提⾼。根据Brute-Force算法，遇到不相等的字符，将⼦串后移⼀位，再从头逐个⽐较。这样做虽然可⾏，但是效果很差，因为你要将主串和⼦串的指针都退回到原来的位置，将已经⽐较过的字符重新⽐较⼀遍。KMP算法思想是：在每⼀趟匹配过程中出现字符不等时，不需要回退主串的指针，⽽是利⽤已经得到前⾯“部分匹配”的结果，将模式串向右滑动若⼲个字符后，继续与主串中的当前字符进⾏⽐较。假设主串S="ababcabcacbab"模式串T="abcac"。KMP算法匹配过程如图 从图中可以看出，KMP算法的匹配次数从原来的6趟减少为3趟。⽽对于Brute-Force算法，在第3趟匹配过程中，当i=6,j=4时，主串中的字符与模式串中的字符不相等，⼜从i=3,j=0开始⽐较。经过仔细观察，其实在i=3,j=0,i=4,j=0,i=5,j=0这三次⽐较过程都是没有必要的。因为从第3趟的部分匹配课得出：S2=T0='a',S3=T1='b',S4=T2='c',S5=T3='a',S6≠T4,因为S3=T1且T0≠T1,所以S3≠T0，所以没有必要从i=3、j=0开始⽐较。⼜因为S4=T2,且T0≠T2，故S4≠T0，所以S4与T0也没有必要从i=4、j=0开始⽐较。⼜因为S5=T3且T0=T4，故S5=T0,所以也没有必要将S5与T0进⾏⽐较。也就是说，根据第3趟的部分匹配也可以得出结论：Brute-Force算法算法的第4、5趟是没有必要的，第6趟也没有必要将主串的第6个字符与模式串的第1个字符⽐较。因此，只需要将模式串向右滑动3个字节，从i=6，j=1开始⽐较。同理，在第1 趟匹配的过程中，当出现字符不相等时，只需将模式串向右滑动2个字符，从i=2、j=0开始⽐较即可。在整个KMP算法中，主串中的i指针没有回退。下⾯来讨论⼀般情况。设主串S=“sn-1”模式串T=“-1”。在模式匹配过程中，若出现字符不匹配的情况，即当si≠tj（0≤ik满⾜以上等式。计算next[j+1]的值需要考虑以下两种情况：（1）若tj=tk，则表⽰在模式串T中满⾜以下关系："t0 t1 ... tk" = "tj-k tj-k+1 ... tj"并且不可能存在k'>k满⾜以上等式。因此有next[j+1]=k+1，即next[j+1]=next[j]+1（2）若tj≠tk，则表⽰模式串T中满⾜以下关系："t0 t1 ... tk" ≠ "tj-k tj-k+1 ... tj"此时，已经有"t0 t1 ... tk-1" = "tj-k tj-k+1 ... tj-1"，但是tj≠tk，把模式串T向右滑动到k'=next[k]（0

例如，在已经得到的前3个字符next函数值的基础上，如果求next[3]。因为next[2]=1，且t2=t0，则next[3]=next[2]+1=2。接着求next[4]，因为t2=t0，但“t2t3”≠“t0t1”，所以需要将t3与下标为next[1]=0的字符即t0进⾏⽐较，因为t0≠t3，所以next[4]=1。