从右到左比较模式和文本字符比从左到右比较有什么优势吗？
这是《算法设计与分析导论》中的练习。这是一个字符串匹配问题。假设我有字符串 ABCD，并且有模式 XY。并想看看字符串是否包含模式。
我们假设这里使用暴力破解，所以从左到右的比较是比较 A 和 X，接下来是比较 B 和 X，等等。而从右到左的比较是比较 B 和 Y，接下来是比较 C提示说从右到左比较确实有优势，但我不明白为什么。
任何提示都很感激！
This is the exercise in "Introduction to The Design and Analysis of Algorithms". It's a string matching issue. Say I have string ABCD, and have a pattern XY. And want to see if the string contains the pattern.
We just assume to use brute-force here, so the left-to-right comparison is comparing A with X, next is comparing B with X, etc. While right-to-left comparison is comparing B with Y, next is comparing C with B. The hint says right-to-left comparison does have the advantage, but I don't see why.
Any hint is appreciate!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
是的。
另请参阅
作为一个极端的示例，考虑如果我们需要在文本
12345678中找到模式ABCD。最早可能的匹配当然从文本的开头开始。我们尝试向后匹配模式，看看是否可以将
D与文本的第 4 个字符匹配。这不是匹配，因此我们知道尝试将
ABC与前 3 个字符匹配是没有意义的。我们还知道（在线性时间预处理之后）我们找到的字符4根本没有出现在模式中，因此我们能找到的最早可能的匹配必须从下一个位置开始，即第5个字符。我们再次尝试向后匹配，看看是否可以将
D与第 8 个字符匹配。我们找到
8；这不是一场比赛。因此该模式不会出现在文本中。我们只需要从文本中看到 2 个字符。这是 Boyer-Moore 算法的一个重要特征：对于长度为
N的文本和长度为M的固定模式，平均情况性能为N /M比较。也就是说，一开始可能有点违反直觉，我们寻找的模式越长，通常找到它的速度就越快。Yes.
See also
As an extreme example, consider if we need to find the pattern
ABCDin the text12345678.The earliest possible match of course starts at the beginning of the text. We try to match the pattern backward, so we see if we can match
Dwith the 4th character of the text.This is not a match, so we know there's no point in trying to match
ABCwith the first 3 characters. We also know (after linear time pre-processing) that the character we find,4, doesn't appear in the pattern at all, so the earliest possible match we can find must start at the next position, i.e. 5th character.Again we try to match backward, so we see if we can match
Dwith the 8th character.We find
8; this is not a match. Therefore the pattern doesn't appear in the text. We only needed to see 2 characters from the text.This is one important characteristics of the Boyer-Moore algorithm: for a text of length
Nand a fixed pattern of lengthM, the average-case performance isN/Mcomparison. That is, perhaps somewhat counterintuitively at first, the longer the pattern we are looking for, the faster we can usually find it.当您发现 Y 与 B 不匹配时，您接下来要比较的两个字符是什么？如果您不断重复这些步骤，在覆盖整个字符串之前您会进行多少次比较？您会与“暴力”方法进行多少次比较？
When you find that Y doesn't match B, what are the next two characters you would compare? If you kept repeating these steps, how many comparisons would you make before you covered the whole string? How many comparisons would you make with the "brute-force" approach?