Алгоритми та структури даних · Senior · Запитання 22 з 75
Як KMP досягає пошуку підрядка за O(n + m)?
- 1Він заздалегідь хешує кожен підрядок тексту
- ✓Правильна відповідь: Префікс-функція каже, на скільки зсунутися, не перечитуючи текст
- 3Він сортує символи тексту й шукає шаблон бінарним пошуком
Пояснення
Для кожної позиції шаблону префікс-функція зберігає довжину найдовшого власного префікса, що водночас є суфіксом. При розбіжності шаблон стрибає на цю величину, тож вказівник у тексті ніколи не йде назад.