Oleksii Trekhleb | Javascript algorithms (Knuth–morris–pratt algorithm)
This is a series of books diving deep into the core mechanisms of the JavaScript language.
· 1 phút đọc.
![nhavantuonglai This is a series of books diving deep into the core mechanisms of the JavaScript language.](https://data.nhavantuonglai.com/image/illustrations/cover-nhavantuonglai-com-0554.jpg)
The Knuth–Morris–Pratt string searching algorithm (or KMP algorithm) searches for occurrences of a word W
within a main text string T
by employing the observation that when a mismatch occurs, the word itself embodies sufficient information to determine where the next match could begin, thus bypassing re-examination of previously matched characters.
Complexity
Time:
O(|W| + |T|)
(much faster comparing to trivialO(|W| |T|)
)Space:
O(|W|)
![nhavantuonglai nhavantuonglai](https://data.nhavantuonglai.com/image/illustrations/cover-nhavantuonglai-com-0127.jpg)