|
|
|
串的运算是串的重点和难点，特别是顺序串上子串定位的运算。
|
|
|
|
子串定位运算又称串的"模式匹配"或"串匹配"，即在主串中查找出子串出现的位置，实际应用中非常广泛，如文本编辑中的"查找和替换"用到的就是子串定位运算的算法。
|
|
|
|
在串匹配中，将主串称为目标（串），子串称为模式（串），子串如同一个模板（样本），用其在目标上从头往后比较查找，若找到和子串一样的一个连续子序列，则称匹配成功，并返回其相应的起始位置。
|
|
|
|
经典的模式匹配算法——Brute-Force的思想是：从目标串s=s0s1…Sn-1的第一个字符开始和模式串t=t0t1…tm-1中的第一个字符比较，若相等，则继续逐个比较后继字符；否则，从目标串s的第二个字符开始重新与模式串t的第一个字符进行比较，依次类推。若存在模式串的每个字符依次和目标串中的一个连续字符序列相等，则匹配成功，函数返回模式串t中第一个字符在主串s中的位置；否则匹配失败，函数返回-1。
|
|
|
|
Brute-Force算法在进行模式匹配过程中，指向主串的指针经常回溯，因而在某些情况下时间复杂度较高，为此，提出了KMP算法。
|
|
|
|
KMP算法是由D.E.Knuth、J.H.Morris和V.R.Pratt共同提出的，所以称为Knuth-Morris-Pratt算法，简称KMP算法。该算法比Brute-Force算法有较大改进，主要是消除了主串指针的回溯，从而使算法效率有一定程度的提高。
|
|
|
|
设s=s0s1…sn-1，t=t0t1…tm-1，当si≠tj(0≤i≤n-m, 0≤j
|
|
|
|
|
|
|
|
|
|
则由式（3-1）说明模式串中的子串t0t1…tk-1已和主串si-ksi-k+1…si-1匹配，下一次可直接比较si和tk，若不存在式(3-2)，则结合式(3-1)说明在t0t1…tj-1中不存在任何以t0为首字符的子串与si-jsi-j…si-1中以si-1为末字符的匹配子串，下一次可直接比较si和t0。
|
|
|
|
|
|
|
|
若模式串t中存在真子串t0t1…tk-1=sj-ksj-k+1…sj-1，且满足0i）不相等时，模式串中需要重新和主串中该字符si进行比较的字符位置为k，即下一次开始比较Si和tk；若不存在这样的真子串，next[j]=0，则下一次开始比较si和t0；当j=0时，令next[j]=-1，此处-1为一个标记，表示下一次开始比较si+1和t0，称每次进行了模式串的右滑。模式串右滑后若仍有si≠tk，则这个模式串的右滑过程可一直进行，直到next[j]=-1时，模式串不再右滑，下一次开始比较si+1和t0。简言之，KMP算法对Brute-Force算法的改进就是利用已经得到的部分匹配结果将模式串右滑一段距离后再继续比较，而无须回溯主串指针。
|
|
|
|
KMP算法的思想是：设s为目标串，t为模式串，并设i指针和j指针分别指示目标串和模式串中正待比较的字符，令i和j的初值均为0。若有si和tj相等，则i和j分别增1；否则，i不变，j退回到j=next[j]的位置（即模式串右滑），比较si和tj，若相等则i和j指针分别增1，否则j再退回到下一个j=next[j]的位置（即模式串继续右滑），再比较si和tj。依次类推，直到下列两种情况之一：一种是j退回到某个j=next[j]时有si=tj，则指针各增1后继续匹配；另一种是j退回到j=-1时，令指针各增1，即下一次比较si+1和t0。
|
|
|
|
但前面介绍的next函数在某些情况下尚有缺陷，这就是说，若按上述定义得到next[j]=k，而模式中tj=tk，则当主串中字符si和tj比较不等时，不需要再和tk进行比较，而直接和tnext[k]进行比较，换句话说，此时的next[j]应和next[k]相同。因而可得nextval[j]的值。
|
|
|
