Понимание Бойера-Мура визуально

Question

Я уже исследовал различные решения Stackru, чтобы попытаться понять, как функционирует алгоритм Бойера-Мура, однако я ищу более-менее пошаговую иллюстрацию о том, как на самом деле функционирует алгоритм (визуальное обучение для меня гораздо лучше).

Я пытаюсь понять это изображение, но я не совсем понимаю, почему при сравнении 6 оно пропускает:

Я бы предпочел, чтобы это выглядело лучше, но если вы расскажете мне через псевдокод, почему это происходит, я буду признателен.

Спасибо.

Answer 1

Самая важная вещь в алгоритме Бойера Мура - это последняя таблица вхождений, которая представляет собой предварительную обработку шаблона. Он хранит последний индекс, в котором появился каждый отдельный символ в шаблоне.

Шаги можно разбить, как показано ниже, где я немного изменил вашу визуализацию.

Шаги переключения объясняются ниже.

1. Символ текста a несовпадение с символом шаблона b . Символ a появляется в последней таблице вхождений с индексом 4. Сдвинуть шаблон так, чтобы индекс 4 выровнялся с несоответствующим текстовым символом a .

2. Текст символов несоответствие с узором символов с . Символ a появляется в последней таблице вхождений с индексом 4. Сдвиг шаблона таким образом, чтобы индекс 4 выровнялся с несоответствующим текстовым символом a , сместил бы шаблон назад. Это не имеет смысла, поэтому все, что мы можем сделать, это сдвинуть шаблон на 1.

3. Символ текста a несовпадение с символом шаблона b . Символ a появляется в последней таблице вхождений с индексом 4. Сдвинуть шаблон так, чтобы индекс 4 выровнялся с несоответствующим текстовым символом a .

4. Несоответствие символа d текста и символа образца b . Символ d не появляется в последней таблице вхождений. Таким образом, мы можем сдвинуть всю картину за пределы этого несоответствия.

5. Символ текста a несовпадение с символом шаблона b . Символ a появляется в последней таблице вхождений с индексом 4. Сдвинуть шаблон так, чтобы индекс 4 выровнялся с несоответствующим текстовым символом a .

6. Все символы совпадают, т.е. у нас есть полное совпадение. Сдвиньте узор наивно на 1.

7. Тот же сценарий, что и для сравнения 7. Совместите индекс шаблона 4 с несоответствующим текстовым символом a .

8. Тот же сценарий, что и выше.

9. Точный сценарий, как для сравнений 2, 3 и 4. Сдвинуть шаблон на 1.

10. Несоответствие текстового символа b символу шаблона a . Мы дошли до конца текста, так что все готово.