сьому тексту ( кроків), стало бути, загальний час роботи є . Тут не враховується час на обчислення хеш-функції. Тому що сама ідея алгоритму побудована на умови, що хеш-функція буде легко обчислюватися, і час цієї обчислення не впливатиме на роботу алгоритму. Прикладом такої легко обчислюється хеш-функції може бути функція, яка вважає суму кодів символів слова в В«віконечкуВ». Таким чином, при зсуві В«віконечкаВ» на один елемент вправо не потрібно заново вважати всю суму. Досить просто відняти код першого символу до зсуву і додати код нового символу, що потрапив у діапазон. Збіг підрахованого значення суми зі значенням хеш-функції шуканого слова при їх посимвольного невідповідність не дуже ймовірно, однак, в гіршому випадку час роботи буде . Широке поширення алгоритм Рабіна не отримав, проте, він часто використовується в програмах пошуку плагіату [2].
.3 Ефективні алгоритми пошуку підрядка в рядку
Алгоритм послідовного пошуку і алгоритм Рабіна-Карпа є алгоритмами з найменшими трудовитратами, тому вони годяться для використання при вирішенні деякого класу задач. Однак ці алгоритми не є найбільш ефективними та оптимальними. Як говорилося раніше, вони часто виконують непотрібну роботу. Тому буде розглядатися наступний клас алгоритмів, які з'явилися в результаті ретельного дослідження алгоритму послідовного пошуку. Дослідники хотіли знайти способи більш повно і корисно використовувати інформацію, отриману під час сканування. На відміну від найпростіших алгоритмів, які дану інформацію не використовують зовсім. p align="justify"> Однак ці алгоритми використовують трохи більше трудовитрат і мають час попередньої обробки. Але операцій порівняння стає в рази менше, і ми можемо говорити про лінійної залежності цих алгоритмів від величини рядка . [5]
.3.1 Алгоритм Кнута-Морріса-Пратта
Даний алгоритм був запропонований в 1977 році вченими Кнутом, Праттом і незалежно від них Морісом. Запропонований ними метод виконує попередню обробку шуканої рядка. На її основі створюється префікс-функція, яка інкапсулює відомості про те, якою мірою зразок співпадає сам із собою після зрушень. Тобто префиксной функцією заданого зразка називається функція , така що
. (1)
Іншими словами, одно довжині найбільшого префікса зразка , який є істинним суфіксом рядка . Як приклад наведемо повну префіксних функцію для зразка ababababca, продемонстровану на рис. 1.
В
Рис.1. Ілюстрація для зразка P = ababababca і q = 8...
