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

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

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

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

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

Проверка на вхождение в качестве подпоследовательности

Даны две последовательности x[1..n] и y[1..k] целых чисел. Выяснить, является ли вторая последовательность подпоследовательностью первой, т.е. можно ли из первой вычеркнуть некоторые члены так, чтобы осталась вторая. Число действий порядка n+k.

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

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

Поиск наидлиннейшей подпоследовательности символов (longest common subsequence, lcs) , общей для двух строк. Эти два вопроса очень близки между собой. Даны мощные и эффективные алгоритмы.

Поиск самой тяжелой общей подпоследовательности
- самой длинной возрастающей подпоследовательности
- самой тяжелой общей подпоследовательности

Самая тяжелой общей подпоследовательность (heaviest common subsequence, hcs) – это последовательность, общая для x и y, имеющая при данной весовой функции максимальную сумму весов компонент. В общем случае, функция может зависеть как от самих символов, так и от их положения в исходных строках.

Самая длинная возростающая подпоследовательность (lis) – это максимальная подпоследовательность строк, компоненты которой, при заданном линейном упорядочении алфавита, строго возрастают.

Самая тяжелая возрастающая подпоследовательность (his) – это возрастающая подпоследовательность с максимальным весом.

Алгоритмы решений тесно связаны, а потому даны вместе.

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

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

Нахождение общих элементов двух массивов

Даны два возрастающих массива целых чисел x[1..k] и y[1..l]. Найти количество тех целых t, для которых t = x[i] = y[j] для некоторых i и j). (Число действий порядка k+l.).

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

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

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

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

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

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

Информацию о решении конкретных задач можно также найти в разделе Олимпиадные задачи: поиск.

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

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

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

Fundamental Algorithms for A Declarative Pattern Matching System

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

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