. br/>
Сенс префікс-функції в тому, що можна відкинути свідомо невірні варіанти, тобто якщо при пошуку збіглася підрядок abcasdqtabc (наступний символ не співпав), то має сенс продовжувати перевірку вже з четвертого символу (перші три і так співпадуть). Метод КМП використовує предобработку шуканої рядка, а саме: на її основі створюється префікс-функція. При цьому використовується наступна ідея: якщо префікс (він же суфікс) рядки довгою більше одного символу, то він одночасно і префікс підрядка довгою . Таким чином, перевіряється префікс попередньої підрядка, якщо ж той не підходить, то префікс її префікса, і т.д. Діючи так, знаходиться найбільший шуканий префікс [4, 5, 7].
Час роботи даної префікс-функції лінійно. Т.к. привласнення префікс-функції відбувається раз, отже, робота цієї функції . Час роботи самого алгоритму також лінійно і дорівнює .
1.3.2 Алгоритм Бойєр-Мура
Алгоритм Бойєр-Мура, розроблений двома вченими - Бойером і Муром в 1977 році, вважається найбільш швидким серед алгоритмів загального призначення, призначених для пошуку підрядка в рядку. Перевага цього алгоритму в тому, що за допомогою деякої предобработки шуканої рядки, зразок порівнюється з вихідним текстом не у всіх позиціях - частина перевірок пропускаються як свідомо не дають результату. p align="justify"> Оригінальний варіант алгоритму Бойєр-Мура складається з двох етапів. На першому етапі будується таблиця зміщень для шуканого зразка. Далі поєднується початок рядка і зразка і починається перевірка з останнього символу зразка. Якщо останній символ зразка та відповідний йому символ рядка не збігаються, то зразок зрушується щодо рядка на величину, отриману з таблиці зміщень, і знову проводиться порівняння, починаючи з останнього символу зразка. В іншому випадку, при збігу символів, проводиться порівняння передостаннього символу зразка і т. д. Якщо всі символи зразка співпали з відповідними символами рядки, то потрібна підрядок знайдена. Якщо ж якийсь (не останній) символ зразка не співпадає з відповідним символом рядка, то зразок зрушується на один символ вправо і знову починається перевірка з останнього символу. p align="justify"> Таблиця зсувів будується на наступних підставах: зрушення шуканого зразка повинен бути мінімальним, таким, щоб не пропустити входження зразка в рядку. Якщо даний символ рядка зустрічається у зразку, то він зсувається таким чином, щоб символ рядка збігся з самим правим входженням цього символу у зразку. Якщо ж шукана рядок взагалі не містить цього символу, то зразок переміщається на величину, що дорівнює його довжині, так що перший символ зразка накладається на наступний символ рядка. Величина зміщення для кожного символу шуканої рядка залежить тільки від порядку символів в ній самій, то...
