algorithm - 为什么 2 种情况下的第 2 步不同？

Question

在将Boyer–Moore 字符串搜索算法应用于字符串时：

SSIMPLE EXAMPLE

有一个模式：

EXAMPLE

算法流程如下：

SSIMPLE EXAMPLE ---------------------(1)
EXAMPLE

SSIMPLE EXAMPLE ----------------------------(2)
      EXAMPLE

SSIMPLE EXAMPLE ----------------------------------(3)
        EXAMPLE

但是当将相同的算法应用于相同的字符串时：

SSIMPLE EXAMPLE

但模式略有不同：（将第一个 E 替换为 T）

TXAMPLE

算法流程如下：

SSIMPLE EXAMPLE ------------------- (1)
TXAMPLE

SSIMPLE EXAMPLE ----------------------(2)
       TXAMPLE

SSIMPLE EXAMPLE ---------------------------(3)
        TXAMPLE

从第一个例子： 在第二步，E是在E

而在第二个例子中： 在第二步中，T不是在空格下E而是在空格下

这是为什么 ？T字母表和分别E在单词TXAMPLE和中有什么区别EXAMPLE？

Answer 1

在EXAMPLE中，第一个字符和最后一个字符是相同的，所以如果匹配最后一个字符，那么你就知道字符串在那个位置有一个E。因此，当您尝试移动EXAMPLE 时，您必须假设该位置的E 与示例中的第一个E 匹配。

在 TXAMPLE 中，最后一个字符仅出现在字符串的末尾，因此如果匹配最后一个字符，则可以将字符串移动到下一个尝试的匹配与第一个完全不重叠的位置，因为 E 不' 不匹配字符串末尾以外的任何地方。