UK 
EnglishТипова
Polski🔎 Пошук рядка КМП — функція відмови
Кнут-Морріс-Пратт шукає в тексті за O(n+m): префіксна функція відмови дозволяє шаблону зсуватися вперед без повторної перевірки збіглих символів. Дивіться, як курсор ніколи не вертається назад.
Про пошук рядка КМП
Алгоритм Кнута-Морріса-Пратта (КМП) розв'язує задачу пошуку рядка — знаходження всіх входжень шаблону P довжини m у тексті T довжини n — за O(n + m) часу, порівняно з наївним найгіршим випадком O(mn). Ключова ідея, опублікована Дональдом Кнутом, Воном Праттом і Джеймсом Морісом 1977 року, — функція відмови (також звана префіксною функцією): попередньо обчислена таблиця, що кодує для кожної позиції шаблону довжину найдовшого власного префікса, який є також суфіксом. Коли трапляється незбіг, алгоритм використовує цю таблицю, щоб зсунути шаблон уперед, не перевіряючи повторно жодного вже обробленого символу тексту.
Симуляція анімує два вказівники — один над текстом, інший над шаблоном — підсвічуючи збіглі символи зеленим, а незбіги червоним. Ви побачите, як будується таблиця функції відмови, як шаблон зсувається вперед при незбігу, і зможете порівняти загальну кількість порівнянь символів із наївним лічильником грубої сили, показаним поруч.
Часті запитання
Чому КМП швидший за наївний пошук рядків?
Наївний пошук може багато разів повторно розглядати ті самі символи тексту: для тексту на кшталт "AAAAAAB" зі зразком "AAAB" він виконує O(nm) порівнянь у найгіршому випадку. КМП уникає цього, ніколи не рухаючи вказівник тексту назад; кожен символ розглядається щонайбільше двічі (один раз під час побудови функції відмови, один раз під час пошуку), що дає тверду гарантію O(n + m) незалежно від вхідних даних.
Що таке функція відмови (префіксна функція)?
Для шаблону P функція відмови π[i] дає довжину найдовшого власного префікса P[0..i], який є також суфіксом P[0..i]. Наприклад, для шаблону "ABAB" π = [0, 0, 1, 2]. Коли на позиції i шаблону трапляється незбіг, алгоритм встановлює i = π[i−1] замість скидання до 0, тому раніше збіглі символи не порівнюються повторно.
Яка часова складність побудови функції відмови?
Побудова таблиці відмови займає O(m) часу та O(m) пам'яті за допомогою двовказівникового сканування самого шаблону. Разом із фазою пошуку O(n) загальна складність становить O(n + m). Доведення використовує амортизований аргумент: хоча внутрішній цикл може ітерувати, змінна, що відстежує довжину збігу, може зростати лише n разів за весь пошук.
Як КМП обробляє перетинні збіги?
Коли на позиції i тексту знайдено повний збіг, алгоритм встановлює вказівник шаблону на π[m−1], а не на 0, дозволяючи одразу шукати наступний перетинний збіг. Наприклад, пошук "ABA" у "ABABA" правильно знаходить збіги на позиціях 0 і 2.
Чи є КМП найшвидшим алгоритмом пошуку рядків на практиці?
Не завжди. Хоча КМП досягає теоретичної межі O(n + m), такі алгоритми, як Бойєр-Мур-Горспул, часто перевершують його на практиці, оскільки можуть пропускати багато символів одразу, використовуючи евристики поганого символу та доброго суфікса, що дає сублінійну поведінку в середньому випадку на типовому англійському тексті. КМП кращий, коли алфавіт малий (наприклад, основи ДНК A/C/G/T) або коли потокові вхідні дані виключають забігання вперед.
Де КМП використовується в реальному програмному забезпеченні?
КМП та споріднені алгоритми використовуються в grep, текстових редакторах, інструментах біоінформатики (вирівнювання послідовностей ДНК), системах виявлення мережевих вторгнень (пошук шаблонів у корисних навантаженнях пакетів) і скануванні сигнатур антивірусів. Ядро Linux використовує варіацію для пошуку рядків у модулях ядра.
У чому різниця між КМП та алгоритмом Ахо-Корасік?
КМП шукає один шаблон за лінійний час. Ахо-Корасік узагальнює це для одночасного пошуку k шаблонів за O(n + m₁ + … + mₖ + z) часу (z = загальна кількість збігів), використовуючи скінченний автомат, побудований з усіх шаблонів. Це алгоритм, що лежить в основі таких інструментів, як fgrep, та систем перевірки мережевого вмісту.
Чи може КМП обробляти текст у Юнікоді?
Так, за умови правильного порівняння символів. КМП оперує послідовностями токенів (кодовими точками або байтами), тож працює з будь-яким алфавітом. При роботі з текстом у кодуванні UTF-8 зазвичай оперують байтами, але потрібна обережність поблизу меж багатобайтових символів, щоб уникнути розділення кодової точки посередині збігу.
Що таке Z-алгоритм і як він пов'язаний з КМП?
Z-алгоритм обчислює для кожної позиції i в рядку довжину найдовшого підрядка, що починається з i і є також префіксом рядка. Він розв'язує ту саму задачу пошуку шаблону за O(n + m) часу, але використовує інший підхід: конкатенує P + $ + T і обчислює Z-масив, а тоді знаходить збіги там, де Z[i] ≥ m. Багато спортивних програмістів надають перевагу Z-масивам за їхню концептуальну простоту.
Чому вказівник тексту в КМП ніколи не рухається назад?
Це центральний інваріант алгоритму. Функція відмови гарантує, що коли на позиції i шаблону трапляється незбіг, уся інформація про вже проскановані символи тексту закодована в π[i−1]. Тому ніколи не потрібно повторно розглядати символ тексту, який уже було зіставлено, що й дає лінійну межу часу.