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

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

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

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

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

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

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