.NET源码学习 [算法2-数组与字符串的查找与匹配]( 八 ) _生活百科

注意到，对于主串中的某一最长可匹配后缀子串，在当前状态下是已经匹配上的。如果在模式串中找到了另一个合法的最长可匹配前缀子串，那我们就将其进行滑动。说明，如果可以滑动，那么在模式串中，一定存在两个不同起始位置的子串，且这两个子串的内容是相同的。因此我们可以用这个信息，在只依赖模式串的情况下完成规律的查找与构建。
数学化表达：对于模式串 t 的每个元素 t[j] ，都存在一个实数 k ，使得模式串 t 开头的 k 个字符（ t[ 0 ], t[ 1 ],…, t[ k-1 ] ）依次与 t[ j ] 前面的 k 个字符（ t[ j-k ], t[ j-k+1 ],…, t[ j-1 ] ）相同（其中，字符 t[ j-k ] 最少从 t[ 1 ] 开始，须保证不重复，所以 k < j ）。。如果这样的 k 有多个，则取最大的一个，以此保证最长。模式串 t 中每个位置 j 的字符都适配这种规律，定义一个 next 数组存储这种规律，即 next[ j ] = MAX{ k } 。

文章插图
对于 next 数组，其索引表示当前比较的两个字符的位置 ‘j’ ；索引对应值表示 k。若当前字符为坏字符，则可以滑动 j – k 位，即下一次的比较位置。
（1）   当模式串的第一个字符和主串不匹配时，并不存在已匹配前缀子串，更不存在最长可匹配前缀子串，因此next数组下标是0 ， next[ 0 ]的元素值也是0 。
（2）   如果已匹配前缀是 “G”、“GT”、“GTGTGC” ，但其并不存在最长可匹配前缀子串，所以对应的next数组元素值（next[ 1 ] ， next[ 2 ] ， next[ 6 ]）同样是0 。
（3）   对于好前缀 “GTG” ，此时比较位置为索引 j = 3 ，从该位置向前找最长可匹配前缀子串；从开头找最长可匹配后缀子串，得出最长可匹配前缀是 ‘G’ ，即 k = 1（此时滑动 j – k = 2 位）。因此，对应数组中的next[ 3 ] ，元素值是k = 1（即，下一次的比较位置）。以此类推， “GTGT” 对应 next[ 4 ] ，元素值是2；“GTGTG“ 对应 next[ 5 ] ，元素值是3 。

文章插图
小结：用一个数组保存每个字符的信息，当在该字符处不匹配时，通过数组保存的信息，退回到相应位置。其中，数组的下标表示“当前比较两个字符的位置 j” ，元素的值则是“最长可匹配前缀子串的下一个位置《=》最长可匹配前缀子串的长度《=》 MAX{ k }” 。
—— —— —— —— —— —— —— —— —— —— —— —— —— ——

如何构建next数组？【重难点】

这个问题其实刚刚已经基本讲述清楚了，现在按照例子再过一遍，掌握这个构建方法，就掌握了KMP的核心。
由于已匹配前后缀子串仅在模式串中查找，与主串无关。所以仅依据模式串，即可生成next数组。
最简单的方法是从最长的前缀子串开始，把每一种可能情况都做一次判断。假设模式串的长度是m ，生成next数组所需的最大总判断次数是1+2+3+4+......+m-2 次。
显然，这种方法的效率非常低，整体近似 n2 的量级。因此，可以采用类似“动态规划”的方法。首先next[ 0 ]和next[ 1 ]的值肯定是0 ，因为不存在前后缀字串；从next[ 2 ]开始， next数组的每一个元素都可以由上一个元素推导而来。