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

文章插图
设置两个变量i和j ，其中i表示“当前比较两字符的位置” ，也就是待填充的数组下标；j表示“最长可匹配前缀子串的下一个位置” ，即转跳回来的下一次比较位置，也就是待填充的元素值。分析可知，此时最长可匹配前缀子串不存在，所以当 i = 0 时， j = 0 ， next[ 0 ] = 0 。

文章插图
继续向后移动当前比较的位置。此时存在字符串 “G“ ，由于只有一个字符，不满足 k < j 的条件。因此，同样不存在最长可匹配前缀子串，所以当 i = 1 时， j = 0 ， next[ 1 ] = 0 。

文章插图
此时的已匹配前缀是 “GT” ，由于模式串当中 pat[ j ] != pat [ i-1 ] ，即’G’ != ‘T’ ，最长可匹配前缀子串仍然不存在。所以当 i = 2 时， j = 0 ， next[ 2 ] = 0 。

文章插图
继续后移。此时的可匹配前缀是 “GTG“ ，此时模式串中 pat [ j ] == pat [ i-1 ] ，即 ‘G‘ = ’G‘ ，最长可匹配前缀子串出现了，是 ”G“ 。

文章插图
所以当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” 去找。