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

—— —— —— —— —— —— —— —— —— —— —— —— —— ——

接下来进一步思考滑动策略的细节：不匹配时，应当滑动到哪里？

举个例子：

文章插图
首先，把主串和模式串的首位对齐，从左到右对逐个字符进行比较。

文章插图
第一轮，发现前5个字符都是匹配的，第6个字符不匹配，将其标记为坏字符 ‘A’ 。

文章插图
【重难点】
可以发现，在好前缀 “GTGTG” 当中，主串的好前缀的后三个字符 “GTG” 和模式串的前三位字符 “GTG” 是相同的。我们分别把这两部分记作可匹配后缀子串与可匹配前缀子串。在之后的比较中，这两部分一定能够匹配上。并且在这两个部分匹配上之前，一定没有其他可能使得模式串成功匹配的情况，这也为选择最长的子串进行滑动提供了保障。因此，我们直接将模式串后移两位，使得这两部分对齐，并开始下一次比较，省去了中间的无效比较。
同理，如果在好前缀中如果存在多个可匹配后缀子串，那么为了能省区更多的无效比较，我们选择找到最长的子串进行滑动。因此，我们的滑动策略为：在主串的好前缀中，找到最长可匹配后缀子串；在模式串中，找到对应的最长可匹配前缀子串。

文章插图
第二轮，我们直接把模式串向后移动两位，让两个 “GTG” 对齐，继续从刚才主串的坏字符 ‘A’ 开始进行比较。

文章插图
此时，主串的字符 ‘A’ 仍然是坏字符，这时候的匹配前缀缩短成了 “GTG” 。

文章插图
按照第一轮的思路，我们来重新确定最长可匹配后缀子串和最长可匹配前缀子串。此时，剩下字符串 “G” 。

文章插图
第三轮，我们再次把模式串向后移动两位，让两个“G”对齐，继续从刚才主串的坏字符A开始进行比较。
……
小结：整体思路是，在主串的好前缀中寻找最长可匹配后缀子串（在好前缀中，从后往前找），在模式串中寻找对应的最长可匹配前缀子串（在已匹配串中，从前往后找），直接把两者对齐，从而实现模式串的快速滑动。
—— —— —— —— —— —— —— —— —— —— —— —— —— ——