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

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

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

Есептің берілуі

Мысалы $T$ жолы Үлгі:Lang-en және $S$ жол тармағы Үлгі:Lang-en берілсін. $T$ жолда $S$ - жол тармағының қай жерінен басталып жазылған орнын немесе индексін табу керек.

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

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

Тағы қараңыз

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

Сілттемелер

• http://algolist.manual.ru/search/esearch/kmp.php