Алгоритм Кнута-Моріса-Прата
Матеріал з Вікіпедії — вільної енциклопедії.
Алгоритм Кнута-Моріса-Прата шукає входження слова W
у рядку S
використовуючи просте спостереження, що коли відбувається невідповідність, то слово містить у собі достатньо інформації, для того щоб визначити, де наступне входження може початися, таким чином пропускаючи кілька разову перевірка попередньо порівняних символів.
Алгоритм був винайдений вченими Дональд Кнут and Vaughan Pratt і незалежно J. H. Morris у 1977, але був опублікований у спільній статті.
[ред.] Зовнішні посилання
[ред.] Література
- Donald Knuth, James H. Morris, Jr, Vaughan Pratt (1977). "Fast pattern matching in strings". SIAM Journal on Computing 6 (2): 323-350.