회문이란 무엇입니까?

회문은 뒤에서 읽어도 앞으로 읽어도 같은 단어, 구, 숫자 또는 문자 시퀀스입니다. 즉, 문자가 바뀌어도 변경되지 않습니다.

예

• "레벨"은 왼쪽에서 오른쪽으로, 오른쪽에서 왼쪽으로 읽으므로 회문입니다.

• "racecar"는 회문입니다.

• "12321"은 회문입니다.

• "madam"은 회문입니다.

가장 긴 회문 부분 시퀀스를 위한 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인 회문 하위 시퀀스가 ​​있음을 의미합니다. 즉. BABCBAB. BBBBB” 및 “BBCBB” 역시 주어진 시퀀스의 회문 부분 시퀀스이지만 가장 긴 부분 시퀀스는 아닙니다. 코드는 동적 프로그래밍을 사용하여 이 길이를 성공적으로 계산하고 반환합니다.

결론

결론적으로, 제공된 PHP 코드는 주어진 문자열에서 가장 긴 회문 부분 시퀀스의 길이를 찾는 동적 프로그래밍 솔루션을 구현합니다. 입력 문자열 "BBABBCAB"로 실행하면 가장 긴 회문 부분 수열의 길이가 7(BABCBAB)임을 올바르게 판단합니다. 그러나 코드에서는 부분 수열 자체를 명시적으로 제공하지 않습니다. 문자가 일치하거나 일치하지 않는 경우를 고려하여 다양한 하위 문자열에 대한 길이 테이블을 작성하여 작동합니다. 알고리즘은 상향식 접근 방식을 사용하여 길이를 효율적으로 계산하여 원하는 결과를 얻습니다.