Поиск в строках, массивах, последовательностях.

Точный поиск подстроки в строке

Нужно найти все вхождения некоторого образца в данный текст.

Нечеткий поиск

Алгоритмы нахождения 'приблизительно' таких же вхождений образца в текст.

Вычисление степени похожести (дистанции) двух строк.

Задача о наибольшей общей подпоследовательности

Поиск наидлиннейшей подпоследовательности символов, общей для двух строк.

Нахождение подпоследовательностей с другими требованиями

Эти три вопроса очень близки между собой. Даны мощные и эффективные алгоритмы.

Нахождение максимальной повторяющейся подстроки

Для данной строки y, |y| = n > 0, найти самую длинную подстроку, встречающуюся в y больше одного раза.

Двоичный (бинарный) поиск элемента в массиве

Поиск элемента в упорядоченном массиве за log n операций.

Интерполяционный поиск элемента в массиве

Более быстрый поиск при условии равномерного распределения элементов. Скорость log log n. Особенно хорош при большом размере базы данных. Быстрее деревьев.

Бинарный поиск с определением ближайших узлов

Cущественное улучшение бинарного поиска, оптимизированное для большого количества обращений и для случая, когда цель поиска отличается от элементов массива и нужно найти, например, между какими из них она расположена.

Архив статей.

Д. Кнут. Сортировка и поиск: 3-й том 'Искусства программирования на ЭВМ'

Разные алгоритмы поиска и сортировки, описанные на серьезном теоретическом уровне.

Fundamental Algorithms for A Declarative Pattern Matching System

Большая книжка, охватывающая практически все разделы и алгоритмы поиска подстроки в строке и вычисления дистанции. Псевдокод на С++.

Вверх по странице, к оглавлению и навигации