Кнут-Моррис-Пратт алгоритмі

Кнут — Моррис — Пратт алгоритмі (КМП-алгоритм) — берілген текст жолында ішкі жол тармағын табу алгоритмін айтамыз.

Алгоритмді алғаш ашқан американ ғалымдары Дональд Кнут және Вон Пратт еді, олар жеке дара өз бетімен тапқан Джеймс Моррис болды.. Өз еңбектірінің жемісін олар 1977 басып шығарды..

Мысалы ${\displaystyle \displaystyle T}$ жолы ағылш. text және ${\displaystyle \displaystyle S}$ жол тармағы ағылш. substring берілсін. ${\displaystyle \displaystyle T}$ жолда ${\displaystyle \displaystyle S}$ - жол тармағының қай жерінен басталып жазылған орнын немесе индексін табу керек.

Егер ${\displaystyle \displaystyle T}$ жолында ${\displaystyle \displaystyle S}$ — тармақ жолы табылмаған болса, онда бұл жолдың ішінде болмайтын бір кері индекс беру керек.

Егер керек болған жағдайда әр жол тармағының берілген текст орныныда бар ма екенін бақалып отыру үшін қосымша функция құруға болады.

• Префикс-функциясы
• Z-функциясы
• Бойер — Мур алгоритмі
• Ахо — Корасик алгоритмі

1. Үлгі:Кітап:CLRS
2. Donald Knuth; James H. Morris, Jr, Vaughan Pratt (1977). "Fast pattern matching in strings". SIAM Journal on Computing 6 (2): 323–350. doi:10.1137/0206024. http://citeseer.ist.psu.edu/context/23820/0. 

Уикикітәпте Примеры реализации алгоритма Кнута — Морриса — Пратта тақырыбымен мына бет бар

Примеры реализации алгоритма КМП

• http://algolist.manual.ru/search/esearch/kmp.php(қолжетпейтін сілтеме)

Дональд Кнут Басылымдары Компьютерде бағдарламалау өнері *"The Complexity of Songs" *Computers and Typesetting *Concrete Mathematics *Surreal Numbers *Things a Computer Scientist Rarely Talks About *Selected papers series Бағдарламалық жасақтама [[TeX|Үлгі:TeX]] *MIXAL (MIX *MMIX *GNU MDK) Шрифттер AMS Euler *Computer Modern *Metafont Сауатты бағдарламалау WEB *CWEB Алгоритмдер Knuth's Algorithm X *Knuth–Bendix completion algorithm *Кнут-Моррис-Пратт алгоритмі *Knuth shuffle *Robinson–Schensted–Knuth correspondence *Trabb Pardo–Knuth algorithm Өзге Dancing Links *Knuth reward check *Knuth Prize *Man or boy test *Quater-imaginary base *-yllion Potrzebie system of weights and measures