Алгоритм Коменц-Вальтер () — запропонований Беатою Коменц-Вальтер алгоритм пошуку рядка. Подібно до алгоритму Ахо-Корасік може шукати водночас декілька підрядків у рядку.
Оснований на алгоритмі Бояра-Мура. Алгоритм Коменц-Вальтер важливий зокрема тим, що був реалізований у другій версії Юнікс-утиліти grep.
Оцінки практичної швидкодії алгоритму різняться: за одними оцінками, його швидкодія не перевищує швидкодію алгоритму Ахо-Корасік(Gusfield; С. 55). За іншими оцінками, його швидкодія в багатьох випадках значно перевищує швидкодію алгоритму Ахо-Корасік(Bruce Watson, 1995; С. 83).
Якщо замість алгоритму Бояра-Мура взяти за основу алгоритм Бояра-Мура-Горспула, то алгоритм Коменц-Вальтер можна дещо спростити, однак його швидкодія для рядка довжиною n та найдовшого ключа L, в найгіршому випадку залишатиметься на рівні (Gusfield; С. 56).
Примітки
Література .
Посилання Beate Commentz-Walter A String Matching Algorithm Fast on Average. Extended Abstract — оригінальна публікація алгоритму.