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

文章插图

文章插图
相当于再一次把变量 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 ] 。
复杂度分析：
现在，该算法第一次计算t的哈希值时，时间复杂度为O(n)；后续计算哈希值因为利用了滑窗的优化只有O(1)；比较字符串的Equals()方法，一般地，可以视为O(1) 。