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

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

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

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

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

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

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

Тағы қараңыз

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

Сілттемелер

Уикикітәп

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

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

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