Было бы какое-либо преимущество в сравнении шаблона и текстовых символов справа налево вместо слева направо?
Это - упражнение во "Введении в Дизайн и Анализ Алгоритмов". Это - проблема сопоставления строк. Скажите, что я имею строку ABCD и имею шаблон XY. И хочу видеть, содержит ли строка шаблон.
Мы просто принимаем для использования "в лоб" здесь, таким образом, слева направо сравнение соответствует X, затем сравнивает B с X, и т.д. В то время как справа налево сравнение сравнивает B с Y, затем сравнивает C с B. Подсказка говорит справа налево, что сравнение имеет преимущество, но я не вижу почему.
Любая подсказка, ценят!
2 ответа
Когда вы обнаружите, что Y не совпадает с B, какие следующие два символа вы бы сравнили? Если вы будете повторять эти шаги, сколько сравнений вы сделаете, прежде чем охватите всю строку? Сколько сравнений вы бы сделали, используя метод "грубой силы"?
Да.
См. Также
В качестве крайнего примера рассмотрим, нужно ли нам найти шаблон ABCD в тексте 12345678 .
Самое раннее возможное совпадение, конечно же, начинается в начале текста. Мы пытаемся сопоставить шаблон в обратном порядке, чтобы проверить, сможем ли мы сопоставить D 4-му символу текста.
?
12345678
ABCD
Это не совпадение, поэтому мы знаем, что нет смысла пытаться сопоставить ABC с первыми тремя символами. Мы также знаем (после предварительной обработки линейного времени), что найденный нами символ, 4 , вообще не появляется в шаблоне, поэтому самое раннее возможное совпадение, которое мы можем найти, должно начинаться со следующей позиции, т.е. 5-й символ.
Мы снова пытаемся найти обратное совпадение, чтобы проверить, сможем ли мы сопоставить D восьмому символу.
?
12345678
ABCD
Находим 8 ; это не совпадение. Поэтому узор не появляется в тексте. Нам нужно было увидеть только 2 символа из текста.
Это одна из важных характеристик алгоритма Бойера-Мура: для текста длиной N и фиксированного шаблона длины M производительность в среднем случае составляет N / M сравнение. Это, возможно, поначалу несколько парадоксально, чем длиннее шаблон, который мы ищем, тем быстрее мы обычно можем его найти .