6

这是“算法设计与分析导论”中的练习。这是一个字符串匹配问题。假设我有字符串 ABCD，并且有一个模式 XY。并想看看字符串是否包含模式。

我们只是假设在这里使用蛮力，所以从左到右的比较是比较 A 和 X，接下来是比较 B 和 X，等等。而从右到左的比较是比较 B 和 Y，接下来是比较 C与 B. 提示说从右到左比较确实有优势，但我不明白为什么。

任何提示表示赞赏！

4

2 回答 2

10

是的。

也可以看看

作为一个极端的例子，考虑我们是否需要ABCD在文本中找到模式12345678。

最早可能的匹配当然从文本的开头开始。我们尝试向后匹配模式，所以我们看看是否可以匹配D文本的第 4 个字符。

   ?    
12345678
ABCD

这不是匹配，所以我们知道尝试匹配ABC前 3 个字符是没有意义的。我们也知道（在线性时间预处理之后）我们找到的字符4, 根本没有出现在模式中，所以我们能找到的最早可能的匹配必须从下一个位置开始，即第 5 个字符。

我们再次尝试向后匹配，所以我们看看是否可以匹配D第 8 个字符。

       ? 
12345678
    ABCD

我们发现8；这不是一场比赛。因此该模式不会出现在文本中。我们只需要从文本中看到 2 个字符。

这是 Boyer-Moore 算法的一个重要特征：对于长度为 的文本和长度N为 的固定模式M，平均情况的性能是N/M比较。也就是说，起初可能有点违反直觉，我们正在寻找的模式越长，我们通常可以越快找到它。

于 2010-06-24T16:40:35.497 回答
0

当您发现 Y 与 B 不匹配时，您接下来要比较的两个字符是什么？如果你不断重复这些步骤，在覆盖整个字符串之前你会进行多少次比较？您会与“蛮力”方法进行多少比较？

于 2010-06-24T17:13:15.400 回答