Алгоритам за претрагу ниски

У информатици, алгоритми за претрагу ниски (алгоритми за сравнивање ниски) су важна класа алгоритама ниски који покушавају да нађу место где се један или неколико ниски (или образаца) налазе унутар веће ниске или текста. Они могу да претражују текст формиран од нормалног алфабета, бинарног алфабета, или ДНК алфабета (A, C, G, T).

Начин кодирања низа може да ограничи опсег применљивих алгоритама за претрагу. На пример ако се користи кодирање променљиве ширине многи алгоритми постају веома спори, те су специфичне адаптације алгоритама неопходне.

Литература

• R. S. Boyer and J. S. Moore, A fast string searching algorithm, Carom. ACM 20, (10), 262–272(1977).
• Thomas H. Cormen; Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein (2001). Introduction to Algorithms (2nd изд.). MIT Press and McGraw-Hill. ISBN 978-0-262-03293-3. CS1 одржавање: Вишеструка имена: списак аутора (веза). Chapter 32: String Matching, pp.906–932.

Спољашње везе

• Pattern matching
• StringSearch