Самая длинная общая проблема подстроки — это проблема поиска самой длинной строки (или строк), которая является подстрокой (или подстроками) двух строк.
Задача отличается от задачи поиска Самая длинная общая подпоследовательность (LCS). В отличие от подпоследовательностей, подстроки должны занимать последовательные позиции в исходной строке.
Например, самая длинная общая подстрока строк ABABC, BABCA это строка BABC длина 4. Другие распространенные подстроки: ABC, A, AB, B, BA, BC, а также C.
Наивным решением было бы рассмотреть все подстроки второй строки и найти самую длинную подстроку, которая также является подстрокой первой строки. Временная сложность этого решения будет O((m + n) × m2), куда m а также n длина строк X а также Y, сколько потребуется (m+n) время для поиска подстроки, и есть m2 подстроки второй строки. Мы можем оптимизировать этот метод, рассматривая подстроки в порядке уменьшения их длины и возвращая значение, как только любая подстрока совпадает с первой строкой. Но временная сложность в наихудшем случае остается неизменной, когда отсутствуют общие символы.
Можем ли мы сделать лучше?
Идея состоит в том, чтобы найти самый длинный общий суффикс для всех пар префиксов строк с помощью динамического программирования, используя отношение:
| 0 (otherwise)
where,
0 <= i – 1 < m, where
m is the length of string X0 <= j – 1 < n, where
n is the length of string Y
Например, рассмотрим строки ABAB а также BABA.
Наконец, самая длинная общая длина подстроки будет максимальной из этих самых длинных общих суффиксов всех возможных префиксов.
Следующее решение на C++, Java и Python находит длину самой длинной повторяющейся подпоследовательности последовательностей. X а также Y итеративно с использованием оптимальное основание собственность проблема ЛКС.
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
#include <iostream> #include <string> #include <cstring> using namespace std; // Функция для поиска самой длинной общей подстроки последовательностей // `X[0…m-1]` и `Y[0…n-1]` string LCS(string X, string Y, int m, int n) { int maxlen = 0; // сохраняет максимальную длину LCS int endingIndex = m; // сохраняет конечный индекс LCS в `X` // `lookup[i][j]` хранит длину LCS подстроки `X[0…i-1]`, `Y[0…j-1]` int lookup[m + 1][n + 1]; // инициализируем все ячейки таблицы поиска 0 memset(lookup, 0, sizeof(lookup)); // заполняем интерполяционную таблицу снизу вверх for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { // если текущий символ `X` и `Y` совпадают if (X[i - 1] == Y[j - 1]) { lookup[i][j] = lookup[i - 1][j - 1] + 1; // обновляем максимальную длину и конечный индекс if (lookup[i][j] > maxlen) { maxlen = lookup[i][j]; endingIndex = i; } } } } // вернуть самую длинную общую подстроку, имеющую длину `maxlen` return X.substr(endingIndex - maxlen, maxlen); } int main() { string X = "ABC", Y = "BABA"; int m = X.length(), n = Y.length(); // Находим самую длинную общую подстроку cout << "The longest common substring is " << LCS(X, Y, m, n); return 0; } |
результат:
The longest common substring is AB
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
class Main { // Функция для поиска самой длинной общей подстроки последовательностей // `X[0…m-1]` и `Y[0…n-1]` public static String LCS(String X, String Y, int m, int n) { int maxlen = 0; // сохраняет максимальную длину LCS int endingIndex = m; // сохраняет конечный индекс LCS в `X` // `lookup[i][j]` сохраняет длину LCS подстроки // `Х[0…i-1]`, `Y[0…j-1]` int[][] lookup = new int[m + 1][n + 1]; // заполняем интерполяционную таблицу снизу вверх for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { // если текущий символ `X` и `Y` совпадают if (X.charAt(i - 1) == Y.charAt(j - 1)) { lookup[i][j] = lookup[i - 1][j - 1] + 1; // обновляем максимальную длину и конечный индекс if (lookup[i][j] > maxlen) { maxlen = lookup[i][j]; endingIndex = i; } } } } // вернуть самую длинную общую подстроку, имеющую длину `maxlen` return X.substring(endingIndex - maxlen, endingIndex); } public static void main(String[] args) { String X = "ABC", Y = "BABA"; int m = X.length(), n = Y.length(); // Находим самую длинную общую подстроку System.out.print("The longest common substring is " + LCS(X, Y, m, n)); } } |
результат:
The longest common substring is AB
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
# Функция поиска самой длинной общей подстроки последовательностей `X[0…m-1]` и `Y[0…n-1]` def LCS(X, Y, m, n): maxLength = 0 # хранит максимальную длину LCS endingIndex = m # сохраняет конечный индекс LCS в `X`. # `lookup[i][j]` хранит длину LCS подстроки `X[0…i-1]` и `Y[0…j-1]` lookup = [[0 for x in range(n + 1)] for y in range(m + 1)] # заполняет интерполяционную таблицу снизу вверх for i in range(1, m + 1): for j in range(1, n + 1): #, если текущий символ `X` и `Y` совпадают if X[i - 1] == Y[j - 1]: lookup[i][j] = lookup[i - 1][j - 1] + 1 # обновляет максимальную длину и конечный индекс if lookup[i][j] > maxLength: maxLength = lookup[i][j] endingIndex = i # возвращает самую длинную общую подстроку, имеющую длину maxLength. return X[endingIndex - maxLength: endingIndex] if __name__ == '__main__': X = 'ABC' Y = 'BABA' m = len(X) n = len(Y) # Найти самую длинную общую подстроку print('The longest common substring is', LCS(X, Y, m, n)) |
результат:
The longest common substring is AB
Временная сложность приведенного выше решения равна O(m.n) и требует O(m.n) дополнительное пространство, где m а также n длина строк X а также Y, соответственно. Пространственная сложность приведенного выше решения может быть улучшена до O(n) поскольку для вычисления LCS строки таблицы LCS требуются только решения для текущей строки и предыдущей строки. Мы также можем хранить в строках только ненулевые значения. Мы можем сделать это, используя хеш-таблицы вместо массивов.
Мы также можем решить эту проблему в O(m + n) время с помощью обобщенного суффиксное дерево. Мы скоро обсудим подход суффиксного дерева в отдельном посте.
Упражнение: Напишите оптимизированный по пространству код для итеративной версии.
Использованная литература: https://en.wikipedia.org/wiki/Longest_common_substring_problem