Некоторые алгоритмы, которые применяются для обработки подпоследовательностей в строках:

• Наивный алгоритм. 1 Перебирает все варианты совмещения подпоследовательностей, но имеет экспоненциальную сложность. 1
• Алгоритм Хиршберга. 1 Построение наибольшей общей подпоследовательности за время O(mn) и объём памяти O(min(m, n)). 1
• Метод динамического программирования Вагнера и Фишера. 2 Прост в реализации, но требует квадратичных затрат времени и памяти. 2 Его идея состоит в том, чтобы последовательно оценивать расстояния между всё более длинными префиксами строк до получения окончательного результата. 2
• Алгоритм Ханта-Шиманского. 2 Во многих приложениях имеет высокую эффективность, но в худшем случае временная сложность становится больше квадратичной. 2
• Алгоритм Машека и Патерсона. 2 Единственный из известных алгоритмов, которому в худшем случае требуется субквадратичное время. 2 Основная идея метода состоит в разбиении матрицы расстояний на совокупность подматриц. 2