🪴 BLOG IT

Обработка строк

3 min read

Обработка строк — это важная часть алгоритмов и структур данных, которая находит широкое применение в текстовых редакторах, биоинформатике, поисковых системах и многих других областях. Два ключевых алгоритма, которые часто используются при обработке строк, — это нахождение наибольшей общей подпоследовательности (LCS, Longest Common Subsequence) и расстояние Левенштейна.

1. Нахождение наибольшей общей подпоследовательности (LCS)

Описание задачи:

Задача нахождения наибольшей общей подпоследовательности состоит в том, чтобы найти наибольшую последовательность символов, которая присутствует в двух строках, не обязательно подряд. В отличие от подстроки, символы в подпоследовательности не обязательно должны идти подряд, но должны сохранять порядок.

Пример:
Для строк X = "ABCBDAB" и Y = "BDCABB" наибольшая общая подпоследовательность будет LCS(X, Y) = "BCAB".

Алгоритм:

Для решения задачи используется динамическое программирование. Мы строим таблицу, в которой элемент dp[i][j] будет хранить длину наибольшей общей подпоследовательности для первых i символов строки X и первых j символов строки Y.

  1. Если символы строк совпадают (X[i] == Y[j]), то длина LCS на позиции dp[i][j] будет равна длине LCS для dp[i-1][j-1] плюс 1.

  2. Если символы не совпадают (X[i] != Y[j]), то длина LCS на позиции dp[i][j] будет равна максимальной длине из двух предыдущих позиций: dp[i-1][j] и dp[i][j-1].

Сложность:

  • Время: O(m * n), где m — длина первой строки, а n — длина второй строки.

  • Память: O(m * n) для хранения таблицы динамического программирования.

Применение:

  • Сравнение текстов (например, для проверки сходства документов).

  • Сравнение биологических последовательностей (например, для поиска схожих частей ДНК).

  • Вычисление схожести строк в текстовых редакторах.

2. Алгоритм редактирования строк (расстояние Левенштейна)

Описание задачи:

Задача вычисления расстояния Левенштейна заключается в нахождении минимального числа операций (вставки, удаления или замены символов), которые необходимо выполнить для преобразования одной строки в другую.

Пример:
Для строк X = "kitten" и Y = "sitting", минимальное расстояние Левенштейна будет равно 3 (изменить “kitten” на “sitting” можно за 3 операции: заменив k на s, вставив i и заменив e на i).

Алгоритм:

Алгоритм также основан на динамическом программировании. Мы строим таблицу, в которой элемент dp[i][j] будет содержать минимальное количество операций, которые необходимо выполнить для преобразования первых i символов строки X в первые j символов строки Y.

  1. Если символы строк совпадают (X[i-1] == Y[j-1]), то dp[i][j] = dp[i-1][j-1].

  2. Если символы не совпадают, то нужно выбрать минимальную операцию (вставка, удаление или замена):

    • Вставка: dp[i][j] = dp[i][j-1] + 1

    • Удаление: dp[i][j] = dp[i-1][j] + 1

    • Замена: dp[i][j] = dp[i-1][j-1] + 1

Сложность:

  • Время: O(m * n), где m и n — длины строк.

  • Память: O(m * n) для хранения таблицы.

Применение:

  • Корректировка текста (например, исправление орфографических ошибок).

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

  • Поиск схожести между биологическими последовательностями.

  • Применяется в поисковых системах для исправления ошибок ввода.

Graph View

Backlinks