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

文章插图
所以当i=3时，j=1，next[ 3 ] = next[ 2 ] + 1 = 1 。

文章插图
继续后移。此时的已匹配前缀是 “GTGT“，由于模式串中 pat [j] == pat [i-1]，即 ‘T’ = ‘T’ ，最长可匹配前缀子串又增加了一位，是 ”GT“ 。

文章插图
所以当i=4时，j=2，next[ 4 ] = next[ 3 ] + 1 = 2 。

文章插图
此时的已匹配前缀是 “GTGTG“ ，由于模式串当中 pat [ j ] == pat [ i-1 ]，即 ‘G’ = ‘G’，最长可匹配前缀子串又增加了一位，是 ”GTG“ 。

文章插图
所以当i=5时，j=3 ， next[ 5 ] = next[ 4 ] + 1 = 3 。

文章插图
此时的已匹配前缀是 “GTGTGC“ 。此时，模式串中 pat [ j ] != pat [ i-1 ]，即 ‘T’ != ‘C’ 。此时无法从next[ 5 ]的值推导出next[ 6 ]，而字符 ‘C’ 的前面又有两段重复的子串“GTG” 。
【重难点】
我们要找的是最长公共前后缀子串，在之前的判断中，我们已经获得了两组满足条件的公共字串 “GT“ 与 ”GTG“ 。既然在当前 ”GTG “ 找不到满足的前缀，那就到上一个前缀 “GT” 去找。

文章插图
相当于把变量j回溯到了next[ j ]，也就是j = 1的局面，在之前的前缀中寻找满足的前后缀子串。

文章插图
回溯后，情况仍然是 pat [ j ] != pat[ i-1 ]，即 ’T’ != ‘C’ 。那就继续回溯。

文章插图

文章插图
相当于再一次把变量 j 退回到了next[ j ]，也就是 j = 0 的局面。

文章插图
情况仍然是 pat [ j ] != pat[ i-1 ]，即 ‘G’ != ‘C’ 。j 已经不能再回溯了，所以得出结论：i=6时，j=0 ， next[ 6 ] = 0 。
小结：
1. 对模式串预处理，生成next数组
1.1 从next[ 2 ]开始，利用动态规划 + 双指针推推出跳转数组。
2. 进入主循环，遍历主串
2.1. 比较主串和模式串的字符。
2.2. 如果发现坏字符，查询next数组，得到匹配前缀所对应的最长可匹配前缀子串，移动模式串到对应位置。
2.3.如果当前字符匹配，继续循环。

文章插图
【注：有关 Line 88 行的分析，仅为个人推断，可能错在错误或解释不清的地方，望各位有想法的大佬及学者留言评论，谢谢！】

Line 88：为什么要加这一句呢？如果是找第一次匹配的位置，那直接 return 结果就好。但是，我们需要找到模式串在主串中所有出现过的位置。这就使得我们需要保证，在找到一次匹配后，需要滑动到某一特定位置，再次开始匹配，且滑动后的位置需要保证不会漏掉任何一种情况。

据之前的分析， j = next[ j ] 表示将 j 回溯到上一个满足的前缀子串的下一次比较位置； j 表示的是当前应滑动到的比较位置。同理 j = next[ j – 1 ] 的含义肯定也是回溯到某一位置上。那为什么是 j – 1 呢？这里个人推断应该有如下两个方面：
（1）越界问题。进入到这个 if 内部的前提是 j == m，而 next 数组的最大索引位 m – 1 。因此，为了防止越界，传入 next 中的值应当在 [0, m – 1] 之内。
（2）合理转化。

文章插图
这是当前的状态，我们可以将当前 j 的位置补一个空白字符，其不与任何一个字符相匹配，因此需要回溯。那么对于当前前缀子串 “ABA#” 其不存在对应的可匹配前后缀子串，根据上面的规则，需要在之前找到一组可匹配的前后缀子串，重新进行判断。而如何滑动到之前的可匹配子串呢？我们可以把 j 的前一位视作当前的比较位置，假设该位置的字符是不匹配的，这样就可以直接回溯到之前的可匹配子串的下一次比较位置。因此，此处位 j = next[ j – 1 ] 。