Коменц-Валтеров алгоритам

Из Википедије, слободне енциклопедије
Jump to navigation Jump to search

У рачунарству Коменц-Валтеров алгоритам је алгоритам који претражује стрингове. Може претраживати више узорака одједном јер се заснива на Ахо-Ќорасик алгоритму претаге стрингова. Комбинује идеје из Ахо-Корасик алгоритма са брзином Бојер-Муровог.

Сложеност[уреди]

За текст од n карактера и дужином узорка L, најгори случај је реда O(n*L), мада се средњи случај, који је знатно бољи, много чешће јавља.

Имплементација[уреди]

GNU-ов алат Grep користи алгоритам јако сличан Коменц-Валтеровом.