Почему двусторонний алгоритм соответствует левой части в обратном порядке?

Question

Двухсторонний алгоритм - это алгоритм поиска подстроки (основная статья, 1,4 МБ PDF).

Он разбивает шаблон поиска x на две части: x = x_l x_r, и сначала он пытается сопоставить x_r с текстом, и в случае успеха алгоритм предписывает сопоставить x_l в обратном порядке (т. Е. Справа налево)).

• Почему x_l соответствует справа налево?
• Могу ли я заменить это сравнение слева направо?

Причина вопроса проста: сравнение с неопределенным заказом уже доступно и, возможно, более производительно, подумайте что-то вроде оптимизированного memcmp или развернутая петля.

Answer 1

С точки зрения эффективности это, очевидно, не имеет значения. Единственная другая причина, о которой я могу подумать: в случае несоответствия, попытка справа налево потенциально оставляет алгоритму больше информации о частичном совпадении. Таким образом, в RTL, если мы сопоставим 2 символа в xl, а затем потерпим неудачу, мы знаем, что имеем частичное непрерывное совпадение 2 символов + xr. Если мы сопоставим xl LTR и потерпим неудачу, мы ничего не знаем, кроме совпадения xr.