Поиск

40] Алгоритм Бойера-Мура

План:

1. Стратегия
2. Реализация
3. Сравнение
4. Промоделировать работу
5. Анализ сложности

Идея:

• Поиск справа налево
• Стоп-символы.

В лучшом случае требует N/M сравнений. Худший варинт O(NM).

Заготовки:

• В чём суть?
• Чем отличается от аналогов?
• Как формируется массив стоп-слов?
• Плохие случаи.

ToDo:

1. Реализовать на Си.