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

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

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

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

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

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

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

Тағы қараңыз өңдеу

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

Сыртқы сілттемелер өңдеу

↑ Үлгі:Кітап:CLRS
↑ 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

[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.

[1]

[2]