Алгоритмы и структуры данных

Самая длинная палиндромная подпоследовательность (Longest Palindromic Subsequence)

LPS — это самая длинная последовательность символов, которая является палиндромом.

Алгоритм поиска LPS:
1. Создаем матрицу dp размером n x n, где n - длина исходной строки.
2. Заполняем главную диагональ матрицы значениями 1, так как каждый символ сам по себе является палиндромом длины 1.
3. Перебираем подпоследовательности строки разной длины и заполняем матрицу dp с помощью следующих правил:
- Если символы на текущих позициях равны, увеличиваем значение dpij на 2 и переходим к следующим символам (i+1, j-1).
- Если символы не равны, выбираем максимальное значение из dpi+1j и dpij-1 и записываем его в dpij.
4. Возвращаем значение dp0n-1, которое представляет длину самой длинной палиндромной подпоследовательности.

Сложность: O(n^2), где n - длина исходной строки.

www.tgoop.com/the_algorithms/4944

4.2K viewsMay 17 at 08:59

Самая длинная палиндромная подпоследовательность (Longest Palindromic Subsequence)

LPS — это самая длинная последовательность символов, которая является палиндромом.

Алгоритм поиска LPS:
1. Создаем матрицу dp размером n x n, где n - длина исходной строки.
2. Заполняем главную диагональ матрицы значениями 1, так как каждый символ сам по себе является палиндромом длины 1.
3. Перебираем подпоследовательности строки разной длины и заполняем матрицу dp с помощью следующих правил:
- Если символы на текущих позициях равны, увеличиваем значение dpij на 2 и переходим к следующим символам (i+1, j-1).
- Если символы не равны, выбираем максимальное значение из dpi+1j и dpij-1 и записываем его в dpij.
4. Возвращаем значение dp0n-1, которое представляет длину самой длинной палиндромной подпоследовательности.

Сложность: O(n^2), где n - длина исходной строки.

BY Алгоритмы и структуры данных