从右到左而不是从左到右比较模式和文本字符会有什么好处吗？

Question

这是"算法设计和分析导论"中的练习.这是一个字符串匹配问题.假设我有字符串ABCD,并且有一个模式XY.并希望查看字符串是否包含模式.

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

任何提示都很感激!

Answer 1

是.

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

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

   ?    
12345678
ABCD

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

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

       ? 
12345678
    ABCD

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

这是Boyer-Moore算法的一个重要特征:对于长度文本N和固定长度模式M,平均情况性能是N/M比较.也就是说,一开始可能有点违反直觉,我们寻找的模式越长,我们通常能够找到它的速度越快.