Content #
当模式串滑动到图中的位置的时候，模式串和主串有 2 个字符是匹配的，倒数第 3 个字符发生了不匹配的情况。
把已经匹配的 bc 叫作好后缀，记作{u}。
模式串中找到了另一个等于{u}的子串 #
拿它在模式串中查找，如果找到了另一个跟{u}相匹配的子串{u*}，那就将模式串滑动到子串{u*}与主串中{u}对齐的位置。
模式串中找不到另一个等于{u}的子串 #
下面的例子中，bc 是好后缀，尽管在模式串中没有另外一个相匹配的子串{u*}，但是如果将模式串移动到好后缀的后面，那就会错过模式串和主串可以匹配的情况。
规则总结 #
规则一：如果好后缀在模式串中不存在可匹配的子串，那在一步一步往后滑动模式串的过程中，只要主串中的{u}与模式串有重合，那肯定就无法完全匹配。规则二：当模式串滑动到前缀与主串中{u}的后缀有部分重合的时候，并且重合的部分相等的时候，就有可能会存在完全匹配的情况。
所以，针对这种情况，不仅要看好后缀在模式串中，是否有另一个匹配的子串，还要考察好后缀的后缀子串，是否存在跟模式串的前缀子串匹配的。
所谓某个字符串 s 的后缀子串，就是最后一个字符跟 s 对齐的子串，比如 abc 的后缀子串就包括 c, bc。所谓前缀子串，就是起始字符跟 s 对齐的子串，比如 abc 的前缀子串有 a，ab。从好后缀的后缀子串中，找一个最长的并且能跟模式串的前缀子串匹配的，假设是{v}，然后将模式串滑动到如图所示的位置。
Viewpoints #
From #
33 | 字符串匹配基础（中）：如何实现文本编辑器中的查找功能？