Что такое палиндром?

Палиндром — это слово, фраза, число или последовательность символов, которые читаются одинаково как в прямом, так и в обратном направлении. Другими словами, он остается неизменным, когда его символы меняются местами.

Пример

• "уровень" является палиндромом, потому что он читается одинаково слева направо и справа налево.

• "гоночная машина" — это палиндром.

• "12321" — палиндром.

• «мадам» — палиндром.

PHP-программа для поиска самой длинной палиндромной подпоследовательности

Пусть X[0..n-1] — входная последовательность длины n, а L(0, n-1) — длина самой длинной палиндромной подпоследовательности X[0..n-1]. Если последний и первый символы X совпадают, то L(0, n-1) = L(1, n-2) 2. Иначе L(0, n-1) = MAX (L(1, n-1), L(0, n-2)).

Решение для динамического программирования

 $y)? $x : $y; }

// Returns the length of the
// longest palindromic
// subsequence in seq
function lps($str)
{
$n = strlen($str);
$i; $j; $cl;

// Create a table to store
// results of subproblems
$L[][] = array(array());

// Strings of length 1 are
// palindrome of length 1
for ($i = 0; $i 

Выход

The length of the longest palindromic subsequence is 7

Вывод данного кода при выполнении с входной строкой «BBABCBCAB» равен Длина самой длинной палиндромной подпоследовательности равна 7. Это означает, что внутри входной строки «BBABCBCAB» существует палиндромная подпоследовательность длиной 7. я .е. БАБКБАБ. BBBBB» и «BBCBB» также являются палиндромными подпоследовательностями данной последовательности, но не самыми длинными. Код успешно вычисляет и возвращает эту длину с помощью динамического программирования.

Заключение

В заключение, предоставленный PHP-код реализует решение динамического программирования для определения длины самой длинной палиндромной подпоследовательности в заданной строке. При выполнении с входной строкой «BBABCBCAB» он правильно определяет, что длина самой длинной палиндромной подпоследовательности равна 7 (BABCBAB). Однако код не предоставляет саму подпоследовательность явно. Он работает путем построения таблицы длин различных подстрок с учетом случаев совпадения или несовпадения символов. Алгоритм эффективно вычисляет длину, используя восходящий подход, что приводит к желаемому результату.