|  |
| Точный поиск подстроки в строке
Нужно найти все вхождения некоторого образца в данный текст.
|
| Нечеткий поиск
Алгоритмы нахождения 'приблизительно' таких же вхождений образца в текст.
|
| Проверка на вхождение в качестве подпоследовательности
Даны две последовательности x[1..n] и y[1..k] целых чисел Выяснить, является ли вторая последовательность подпоследовательностью первой, те можно ли из первой вычеркнуть некоторые члены так, чтобы осталась вторая Число действий порядка n+k.
|
| Общие подпоследовательности. Дистанция
|
| Поиск самой тяжелой общей подпоследовательности, самой длинной возрастающей подпоследовательности, самой тяжелой возрастающей подпоследовательности
Самая тяжелая общая подпоследовательность (heaviest common subsequence, hcs) - это последовательность, общая для x и y, имеющая при данной весовой функции максимальную сумму весов компонент В общем случае, функция может зависеть как от самих символов, так и от их положения в исходных строках
Самая длинная возростающая подпоследовательность (lis) - это максимальная подпоследовательность строк, компоненты которой, при заданном линейном упорядочении алфавита, строго возрастают
Самая тяжелая возрастающая подпоследовательность (his) - это возрастающая подпоследовательность с максимальным весом.
|
| Нахождение максимальной повторяющейся подстроки
Для данной строки y, |y| = n>0, найти самую длинную подстроку, встречающуюся в y больше одного раза.
|
| Нахождение общих элементов двух массивов
Даны два возрастающих массива целых чисел x[1k] и y[1l] Найти количество тех целых t, для которых t = x[i] = y[j] для некоторых i и j) (Число действий порядка k+l).
|
| Двоичный (бинарный) поиск элемента в массиве
Поиск элемента в упорядоченном массиве за log n операций.
|
| Интерполяционный поиск элемента в массиве
Более быстрый поиск при условии равномерного распределения элементов Скорость log log n Особенно хорош при большом размере базы данных.
|
| Бинарный поиск с определением ближайших узлов
Cущественное улучшение бинарного поиска, оптимизированное для большого количества обращений и для случая, когда цель поиска отличается от элементов массива и нужно найти, например, между какими из них она расположена.
|
| Частный случай задачи lis
|
