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

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

Сложеност

[уреди | уреди извор]

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

Имплементација

[уреди | уреди извор]

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