Проблема самой длинной палиндромной подпоследовательности (LPS) заключается в поиске самой длинной подпоследовательности строки, которая также является палиндромом.
Задача отличается от задачи поиска самая длинная палиндромная подстрока. В отличие от подстрок, подпоследовательности не обязаны занимать последовательные позиции в исходной строке.
Например, рассмотрим последовательность ABBDCACB.
The length of the longest palindromic subsequence is 5
The longest palindromic subsequence is BCACB
The longest palindromic subsequence is BCACB
Идея состоит в том, чтобы использовать рекурсия Для решения этой проблемы. Идея состоит в том, чтобы сравнить последний символ строки X[i…j] со своим первым символом. Есть две возможности:
- Если последний символ строки совпадает с первым символом, включить первый и последний символы в палиндром и повторить для оставшейся подстроки.
X[i+1, j-1]. - Если последний символ строки отличается от первого символа, вернуть максимальное из двух значений, которые мы получаем
- Удаление последнего символа и рекурсия для оставшейся подстроки
X[i, j-1]. - Удаление первого символа и рекурсия для оставшейся подстроки
X[i+1, j].
- Удаление последнего символа и рекурсия для оставшейся подстроки
Это дает следующее рекурсивное отношение к нахождению длины самой длинной повторяющейся подпоследовательности последовательности X:
| 1 (if i = j)
LPS[i…j] = | LPS[i+1…j-1] + 2 (if X[i] = X[j])
| max (LPS[i+1…j], LPS[i…j-1]) (if X[i] != X[j])
LPS[i…j] = | LPS[i+1…j-1] + 2 (if X[i] = X[j])
| max (LPS[i+1…j], LPS[i…j-1]) (if X[i] != X[j])
Алгоритм может быть реализован следующим образом на C++, Java и Python. Решение находит длину самой длинной повторяющейся подпоследовательности последовательности X рекурсивно используя приведенные выше соотношения.
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 |
#include <iostream> #include <string> #include <algorithm> using namespace std; // Функция для нахождения длины самой длинной палиндромной подпоследовательности // подстроки `X[i…j]` int findLongestPalindrome(string X, int i, int j) { // Базовое условие if (i > j) { return 0; } // Если строка `X` состоит только из одного символа, это палиндром if (i == j) { return 1; } // Если последний символ строки совпадает с первым символом, if (X[i] == X[j]) { // включить первый и последний символы палиндрома // и повторить для оставшейся подстроки `X[i+1, j-1]` return findLongestPalindrome(X, i + 1, j - 1) + 2; } /* Если последний символ строки отличается от первого символа 1. Удалить последний символ и повторить для оставшейся подстроки `Х[i, j-1]` 2. Удалить первый символ и повторить для оставшейся подстроки `Х[i+1, j]` */ // Возвращаем максимальное из двух значений return max(findLongestPalindrome(X, i, j - 1), findLongestPalindrome(X, i + 1, j)); } int main() { string X = "ABBDCACB"; int n = X.length(); cout << "The length of the longest palindromic subsequence is " << findLongestPalindrome(X, 0, n - 1); return 0; } |
результат:
The length of the longest palindromic subsequence is 5
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 |
class Main { // Функция для нахождения длины самой длинной палиндромной подпоследовательности // подстроки `X[i…j]` public static int findLongestPalindrome(String X, int i, int j) { // Базовое условие if (i > j) { return 0; } // Если строка `X` состоит только из одного символа, это палиндром if (i == j) { return 1; } // Если последний символ строки совпадает с первым символом, if (X.charAt(i) == X.charAt(j)) { // включить первый и последний символы палиндрома // и повторить для оставшейся подстроки `X[i+1, j-1]` return findLongestPalindrome(X, i + 1, j - 1) + 2; } /* Если последний символ строки отличается от первого символа 1. Удалить последний символ и повторить для оставшейся подстроки `Х[i, j-1]` 2. Удалить первый символ и повторить для оставшейся подстроки `Х[i+1, j]` */ return Integer.max(findLongestPalindrome(X, i, j - 1), findLongestPalindrome(X, i + 1, j)); } public static void main(String[] args) { String X = "ABBDCACB"; int n = X.length(); System.out.print("The length of the longest palindromic subsequence is " + findLongestPalindrome(X, 0, n - 1)); } } |
результат:
The length of the longest palindromic subsequence is 5
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 38 |
# Функция для нахождения длины самой длинной палиндромной подпоследовательности # подстроки `X[i…j]` def findLongestPalindrome(X, i, j): # Базовое состояние if i > j: return 0 # Если строка `X` состоит только из одного символа, это палиндром. if i == j: return 1 # Если последний символ строки совпадает с первым символом if X[i] == X[j]: # включает первый и последний символы палиндрома # и повторить для оставшейся подстроки `X[i+1, j-1]` return findLongestPalindrome(X, i + 1, j - 1) + 2 ''' If the last character of the string is different from the first character 1. Remove the last character and recur for the remaining substring `X[i, j-1]` 2. Remove the first character and recur for the remaining substring `X[i+1, j]` ''' # Возвращает максимальное из двух значений return max(findLongestPalindrome(X, i, j - 1), findLongestPalindrome(X, i + 1, j)) if __name__ == '__main__': X = 'ABBDCACB' n = len(X) print('The length of the longest palindromic subsequence is', findLongestPalindrome(X, 0, n - 1)) |
результат:
The length of the longest palindromic subsequence is 5
Временная сложность приведенного выше решения в наихудшем случае экспоненциальна. O(2n), куда n длина входной строки. Наихудший случай возникает, когда в строке нет повторяющегося символа. X (т. е. длина LPS равна 1), и каждый рекурсивный вызов завершается двумя рекурсивными вызовами. Это также требует дополнительного места для стека вызовов.
Проблема LPS имеет оптимальное основание а также экспонаты перекрывающиеся подзадачи. Давайте рассмотрим дерево рекурсии для последовательности длины 6, имеющей все различные символы, скажем ABCDEF, длина LPS которого равна 1.
Как мы видим, одни и те же подзадачи (выделенные одним цветом) вычисляются неоднократно. Мы знаем, что задачи с оптимальной структурой и перекрывающимися подзадачами могут быть решены с помощью динамического программирования, где решения подзадач памяткаизмерено, а не вычислено, и снова. Этот метод демонстрируется ниже на C++, Java и Python:
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 53 54 55 56 57 58 59 60 61 62 63 64 65 |
#include <iostream> #include <string> #include <unordered_map> using namespace std; // Функция для нахождения длины самой длинной палиндромной подпоследовательности // подстроки `X[i…j]` int findLongestPalindrome(string X, int i, int j, auto &lookup) { // Базовое условие if (i > j) { return 0; } // Если строка `X` состоит только из одного символа, это палиндром if (i == j) { return 1; } // Создание уникального ключа карты из динамических элементов ввода string key = to_string(i) + "|" + to_string(j); // Если подзадача видится впервые, решаем ее и // сохраняем результат на карту if (lookup.find(key) == lookup.end()) { /* Если последний символ строки совпадает с первым символом, включать первый и последний символы в палиндром и повторяться для оставшейся подстроки `X[i+1, j-1]` */ if (X[i] == X[j]) { lookup[key] = findLongestPalindrome(X, i + 1, j - 1, lookup) + 2; } else { /* Если последний символ строки отличается от первого персонаж 1. Удалить последний символ и повторить для оставшейся подстроки `Х[i, j-1]` 2. Удалить первый символ и повторить для оставшейся подстроки `Х[i+1, j]` 3. Вернуть максимальное из двух значений */ lookup[key] = max (findLongestPalindrome(X, i, j - 1, lookup), findLongestPalindrome(X, i + 1, j, lookup)); } } // Возвращаем решение подзадачи с карты return lookup[key]; } int main() { string X = "ABBDCACB"; int n = X.length(); // Создаем карту для хранения решений подзадач unordered_map<string, int> lookup; cout << "The length of the longest palindromic subsequence is " << findLongestPalindrome(X, 0, n - 1, lookup); return 0; } |
результат:
The length of the longest palindromic subsequence is 5
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 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 |
import java.util.HashMap; import java.util.Map; class Main { // Функция для нахождения длины самой длинной палиндромной подпоследовательности // подстроки `X[i…j]` public static int findLongestPalindrome(String X, int i, int j, Map<String, Integer> lookup) { // Базовое условие if (i > j) { return 0; } // Если строка `X` состоит только из одного символа, это палиндром if (i == j) { return 1; } // Создание уникального ключа карты из динамических элементов ввода String key = i + "|" + j; // Если подзадача видится впервые, решаем ее и // сохраняем результат на карту if (!lookup.containsKey(key)) { /* Если последний символ строки совпадает с первым символом, включать первый и последний символы в палиндром и повторяться для оставшейся подстроки `X[i+1, j-1]` */ if (X.charAt(i) == X.charAt(j)) { lookup.put(key, findLongestPalindrome(X, i + 1, j - 1, lookup) + 2); } else { /* Если последний символ строки отличается от первого персонаж 1. Удалить последний символ и повторить для оставшейся подстроки `Х[i, j-1]` 2. Удалить первый символ и повторить для оставшейся подстроки `Х[i+1, j]` 3. Вернуть максимальное из двух значений */ lookup.put(key, Integer.max(findLongestPalindrome(X, i, j - 1, lookup), findLongestPalindrome(X, i + 1, j, lookup))); } } // Возвращаем решение подзадачи с карты return lookup.get(key); } public static void main(String[] args) { String X = "ABBDCACB"; int n = X.length(); // Создаем карту для хранения решений подзадач Map<String, Integer> lookup = new HashMap<>(); System.out.print("The length of the longest palindromic subsequence is " + findLongestPalindrome(X, 0, n - 1, lookup)); } } |
результат:
The length of the longest palindromic subsequence is 5
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 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
# Функция для нахождения длины самой длинной палиндромной подпоследовательности # подстроки `X[i…j]` def findLongestPalindrome(X, i, j, lookup): # Базовое состояние if i > j: return 0 # Если строка `X` состоит только из одного символа, это палиндром. if i == j: return 1 # создает уникальный ключ из динамических элементов ввода key = (i, j) # Если подзадача возникает впервые, решите ее и # сохраняет результат в словаре if key not in lookup: ''' If the last character of the string is the same as the first character, include the first and last characters in palindrome and recur for the remaining substring X[i+1, j-1] ''' if X[i] == X[j]: lookup[key] = findLongestPalindrome(X, i + 1, j - 1, lookup) + 2 else: ''' If the last character of the string is different from the first character 1. Remove the last character recur for the remaining substring `X[i, j-1]` 2. Remove the first character recur for the remaining substring `X[i+1, j]` 3. Return the maximum of the two values ''' lookup[key] = max(findLongestPalindrome(X, i, j - 1, lookup), findLongestPalindrome(X, i + 1, j, lookup)) # Вернуть решение подзадачи из словаря return lookup[key] if __name__ == '__main__': X = 'ABBDCACB' # создает словарь для хранения решений подзадач lookup = {} print('The length of the longest palindromic subsequence is', findLongestPalindrome(X, 0, len(X) - 1, lookup)) |
результат:
The length of the longest palindromic subsequence is 5
Временная сложность приведенного выше решения равна O(n2) и требует O(n2) дополнительное пространство, где n длина входной строки.
Однако оба обсуждавшихся выше метода находят только самую длинную длину палиндромной подпоследовательности, но не печатают самую длинную палиндромную подпоследовательность.
Как мы можем напечатать самую длинную палиндромную подпоследовательность?
Задача о самой длинной палиндромной последовательности — классический вариант задачи. Самая длинная общая подпоследовательность (LCS) проблема. Идея состоит в том, чтобы найти ЛВП данной строки с ее реверсом, т. е. вызвать LCS(X, reverse(X)) и самая длинная общая подпоследовательность будет самой длинной палиндромной подпоследовательностью.
Ниже приведена программа на C++, Java и Python, которая демонстрирует это:
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 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 |
#include <iostream> #include <string> #include <algorithm> using namespace std; // Функция для поиска LCS строки `X[0…m-1]` и `Y[0…n-1]` string findLongestPalindrome(string X, string Y, int m, int n, auto &lookup) { // вернуть пустую строку, если достигнут конец любой последовательности if (m == 0 || n == 0) { return string(""); } // Если последний символ `X` и `Y` совпадают if (X[m - 1] == Y[n - 1]) { // добавить текущий символ (`X[m-1]` или `Y[n-1]`) в LCS из // подстрока `X[0…m-2]` и `Y[0…n-2]` return findLongestPalindrome(X, Y, m - 1, n - 1, lookup) + X[m - 1]; } // в противном случае, если последний символ `X` и `Y` различны // если верхняя ячейка текущей ячейки имеет большее значение, чем левая // ячейка, затем отбрасываем текущий символ строки `X` и находим LCS // подстроки `X[0…m-2]`, `Y[0…n-1]` if (lookup[m - 1][n] > lookup[m][n - 1]) { return findLongestPalindrome(X, Y, m - 1, n, lookup); } // если левая ячейка текущей ячейки имеет большее значение, чем верхняя // ячейка, затем отбрасываем текущий символ строки `Y` и находим LCS // подстроки `X[0…m-1]`, `Y[0…n-2]` return findLongestPalindrome(X, Y, m, n - 1, lookup); } // Функция для нахождения длины LCS подстроки `X[0…n-1]` и `Y[0…n-1]` int LCSLength(string X, string Y, int n, auto &lookup) { // первая строка и первый столбец таблицы поиска уже равны 0 // заполняем интерполяционную таблицу снизу вверх for (int i = 1; i <= n; 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; } // иначе, если текущий символ `X` и `Y` не совпадают else { lookup[i][j] = max(lookup[i - 1][j], lookup[i][j - 1]); } } } return lookup[n][n]; } int main() { string X = "ABBDCACB"; int m = X.length(); // lookup[i][j] хранит длину LCS подстроки `X[0…i-1]` и `Y[0…j-1]` vector<vector<int>> lookup(m + 1, vector<int>(m + 1)); // строка `Y` является обратной строкой `X` string Y = X; reverse(Y.begin(), Y.end()); // найти длину LPS с помощью LCS cout << "The length of the longest palindromic subsequence is " << LCSLength(X, Y, m, lookup) << endl; // распечатываем LPS, используя справочную таблицу cout << "The longest palindromic subsequence is " << findLongestPalindrome(X, Y, m, m, lookup); return 0; } |
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 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 |
class Main { // Функция для поиска LCS строки `X[0…m-1]` и `Y[0…n-1]` public static String findLongestPalindrome(String X, String Y, int m, int n, int[][] lookup) { // вернуть пустую строку, если достигнут конец любой последовательности if (m == 0 || n == 0) { return ""; } // Если последний символ `X` и `Y` совпадают if (X.charAt(m - 1) == Y.charAt(n - 1)) { // добавить текущий символ (`X[m-1]` или `Y[n-1]`) в LCS из // подстрока `X[0…m-2]` и `Y[0…n-2]` return findLongestPalindrome(X, Y, m - 1, n - 1, lookup) + X.charAt(m - 1); } // в противном случае, если последний символ `X` и `Y` различны // если верхняя ячейка текущей ячейки имеет большее значение, чем левая // ячейка, затем отбрасываем текущий символ строки `X` и находим LCS // подстроки `X[0…m-2]`, `Y[0…n-1]` if (lookup[m - 1][n] > lookup[m][n - 1]) { return findLongestPalindrome(X, Y, m - 1, n, lookup); } // если левая ячейка текущей ячейки имеет большее значение, чем верхняя // ячейка, затем отбрасываем текущий символ строки `Y` и находим LCS // подстроки `X[0…m-1]`, `Y[0…n-2]` return findLongestPalindrome(X, Y, m, n - 1, lookup); } // Функция для нахождения длины LCS подстроки `X[0…n-1]` и `Y[0…n-1]` public static int LCSLength(String X, String Y, int n, int[][] lookup) { // Заполняем интерполяционную таблицу снизу вверх. // Первая строка и первый столбец таблицы поиска уже равны 0. for (int i = 1; i <= n; 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; } // иначе, если текущий символ `X` и `Y` не совпадают else { lookup[i][j] = Integer.max(lookup[i - 1][j], lookup[i][j - 1]); } } } return lookup[n][n]; } public static void main(String[] args) { String X = "ABBDCACB"; // строка `Y` является обратной строкой `X` String Y = new StringBuilder(X).reverse().toString(); // lookup[i][j] хранит длину LCS подстроки `X[0…i-1]` и `Y[0…j-1]` int[][] lookup = new int[X.length() + 1][X.length() + 1]; // найти длину LPS с помощью LCS System.out.println("The length of the longest palindromic subsequence is " + LCSLength(X, Y, X.length(), lookup)); // распечатываем LPS, используя справочную таблицу System.out.println("The longest palindromic subsequence is " + findLongestPalindrome(X, Y, X.length(), X.length(), lookup)); } } |
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 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 |
# Функция для нахождения LCS `X[0…m-1]` и `Y[0…n-1]` def findLongestPalindrome(X, Y, m, n, lookup): # возвращает пустую строку, если достигнут конец любой последовательности if m == 0 or n == 0: return "" # Если последний символ `X` и `Y` совпадают if X[m - 1] == Y[n - 1]: # добавляет текущий символ (`X[m-1]` или `Y[n-1]`) в LCS # Подстрока # `X[0…m-2]` и `Y[0…n-2]` return findLongestPalindrome(X, Y, m - 1, n - 1, lookup) + X[m - 1] # в противном случае, если последние символы `X` и `Y` отличаются #, если верхняя ячейка текущей ячейки имеет большее значение, чем левая #, затем отбросить текущий символ строки `X` и найти LCS # подстроки `X[0…m-2]`, `Y[0…n-1]` if lookup[m - 1][n] > lookup[m][n - 1]: return findLongestPalindrome(X, Y, m - 1, n, lookup) #, если левая ячейка текущей ячейки имеет большее значение, чем верхняя #, затем отбросить текущий символ строки `Y` и найти LCS # подстроки `X[0…m-1]`, `Y[0…n-2]` return findLongestPalindrome(X, Y, m, n - 1, lookup) # Функция для определения длины LCS подстроки `X[0…n-1]` и `Y[0…n-1]` def LCSLength(X, Y, n, lookup): # Заполните интерполяционную таблицу снизу вверх. # Первая строка и первый столбец интерполяционной таблицы уже равны 0. for i in range(1, n + 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 # в противном случае, если текущий символ `X` и `Y` не совпадают else: lookup[i][j] = max(lookup[i - 1][j], lookup[i][j - 1]) return lookup[n][n] if __name__ == '__main__': X = 'ABBDCACB' # Строка # `Y` является обратной строкой `X` Y = X[::-1] # lookup[i][j] хранит длину LCS подстроки `X[0…i-1]` и `Y[0…j-1]` lookup = [[0 for x in range(len(X) + 1)] for y in range(len(X) + 1)] # найти длину LPS с помощью LCS print('The length of the longest palindromic subsequence is', LCSLength(X, Y, len(X), lookup)) # распечатать LPS с помощью таблицы поиска print('The longest palindromic subsequence is', findLongestPalindrome(X, Y, len(X), len(X), lookup)) |
Output:
The length of the longest palindromic subsequence is 5
The longest palindromic subsequence is BCACB
The length of the longest palindromic subsequence is 5
The longest palindromic subsequence is BCACB
Временная сложность приведенного выше решения равна O(n2) и требует O(n2) дополнительное пространство, где n длина входной строки.
Упражнение: Напишите восходящее решение для приведенной выше рекурсивной нисходящей версии.