가장 긴 회문 부분 수열

가장 긴 회문 하위 시퀀스는 주어진 시퀀스의 하위 시퀀스이며 하위 시퀀스는 회문입니다.

이 문제에서는 하나의 문자 시퀀스가 ​​주어지며 회문 부분 시퀀스의 가장 긴 길이를 찾아야 합니다.

이 문제를 해결하기 위해 재귀 공식을 사용할 수 있습니다.

L(0, n-1)이 가장 긴 회문 부분 수열의 길이를 저장하는 데 사용되는 경우
L (0, n-1) :=L (1, n-2) + 2 (0'번째와 (n-1)번째 문자가 같은 경우).

입력 및 출력

입력:문자나 기호가 다른 문자열. 입력이 "ABCDEEAB"라고 가정합니다. 출력:가장 큰 회문 부분 시퀀스의 가장 긴 길이입니다. 여기 4.ABCDEEAB입니다. 따라서 회문은 AEEA입니다.

알고리즘

palSubSeqLen(str)

입력 - 주어진 문자열입니다.

출력 - 가장 긴 회문 부분 시퀀스의 길이입니다.

begin n =문자열의 길이 nxn 크기의 lenTable이라는 테이블을 만들고 col :=2에서 n에 대해 1로 채우고, i에 대해 수행 :=0에서 n – col, 수행 j :=i + col – 1 str[i] =str[j]이고 col =2이면 lenTable[i, j] :=2 else if str[i] =str[j]이면 lenTable[i, j] :=lenTable[i+ 1, j-1] + 2 else lenTable[i, j] :=lenTable[i, j-1] 및 lenTable[i+1, j]의 최대값 완료 완료 return lenTable[0, n-1]End 
예시
 
#include네임스페이스 사용 std;int max (int x, int y) { return (x> y)? x :y;}int palSubseqLen(문자열 str) { int n =str.size(); int lenTable[n][n]; // (int i =0; i  
출력
 
가장 긴 회문 부분 시퀀스의 길이는 다음과 같습니다. 4