Будет ли какое-нибудь преимущество в сравнении шаблонных и текстовых символов справа налево, а не слева направо?

Question

Это упражнение из раздела «Введение в разработку и анализ алгоритмов». Это проблема соответствия строк. Скажем, у меня есть строка ABCD и шаблон XY. И хотите посмотреть, содержит ли строка шаблон.

Мы просто предполагаем использовать здесь грубую силу, поэтому сравнение слева направо сравнивает A с X, затем сравнивает B с X и т. Д. В то время как сравнение справа налево сравнивает B с Y, затем сравнивает C с B. Подсказка говорит, что сравнение справа налево имеет преимущество, но я не понимаю, почему.

Любая подсказка ценится!

Answer 1

Да.

Смотри также

• Алгоритм поиска строки Бойера – Мура

---

В качестве крайнего примера рассмотрим, нужно ли нам найти шаблон ABCD в тексте 12345678.

Самое раннее возможное совпадение, конечно, начинается в начале текста. Мы пытаемся сопоставить шаблон в обратном направлении, поэтому мы видим, можем ли мы сопоставить D с 4-м символом текста.

   ?    
12345678
ABCD

Это не совпадение, поэтому мы знаем, что нет смысла пытаться сопоставить ABC с первыми 3 символами. Мы также знаем (после предварительной обработки линейного времени), что символ, который мы находим, 4, вообще не появляется в шаблоне, поэтому самое раннее возможное совпадение, которое мы можем найти, должно начинаться со следующей позиции, то есть с 5-го символа.

Снова мы пытаемся сопоставить в обратном направлении, поэтому мы видим, можем ли мы сопоставить D с восьмым символом.

       ? 
12345678
    ABCD

Находим 8; это не совпадение. Поэтому шаблон не появляется в тексте. Нам нужно было только увидеть 2 символа из текста.

Это одна из важных характеристик алгоритма Бойера-Мура: для текста длиной N и фиксированного шаблона длины M средняя производительность в случае сравнения N/M. То есть, возможно, сначала несколько нелогично, чем длиннее шаблон, который мы ищем, тем быстрее мы обычно можем его найти .

Answer 2

Когда вы обнаружите, что Y не соответствует B, какие два следующих символа вы бы сравнили? Если бы вы продолжали повторять эти шаги, сколько сравнений вы бы сделали, прежде чем охватить всю строку? Сколько сравнений вы бы сделали с подходом "грубой силы"?