Trình tự Palindromic dài nhất

Chuỗi con Palindromic dài nhất là dãy con của một dãy đã cho và dãy con là một palindrome.

Trong bài toán này, một dãy ký tự được đưa ra, chúng ta phải tìm độ dài dài nhất của dãy con palindromic.

Để giải quyết vấn đề này, chúng ta có thể sử dụng công thức đệ quy,

Nếu L (0, n-1) được sử dụng để lưu trữ độ dài của dãy con palindromic dài nhất, thì
L (0, n-1):=L (1, n-2) + 2 (Khi ký tự thứ 0 và (n-1) 'giống nhau).

Đầu vào và Đầu ra

 Đầu vào:Một chuỗi với các chữ cái hoặc ký hiệu khác nhau. Giả sử đầu vào là “ABCDEEAB” Đầu ra:Độ dài dài nhất của dãy con palindromic lớn nhất. Đây là 4.ABCDEEAB. Vì vậy, palindrome là AEEA. 

Thuật toán

 palSubSeqLen (str) 

Đầu vào - Chuỗi đã cho.

Đầu ra - Độ dài của dãy con palindromic dài nhất.

 Begin n =length of string, tạo một bảng có tên lenTable có kích thước n x n và điền 1s cho col:=2 to n, do for i:=0 to n - col, do j:=i + col - 1 if str [i] =str [j] and col =2, then lenTable [i, j]:=2 else if str [i] =str [j], then lenTable [i, j]:=lenTable [i + 1, j-1] + 2 else lenTable [i, j]:=max lenTable [i, j-1] and lenTable [i + 1, j] done return lenTable [0, n-1] End  
 Ví dụ 
 
 #include  using namespace std; int max (int x, int y) {return (x> y)? x:y;} int palSubseqLen (string str) {int n =str.size (); int lenTable [n] [n]; // Tạo bảng lưu trữ kết quả của bài toán con for (int i =0; i  
 Đầu ra 
 
 Độ dài của dãy con palindrome dài nhất là:4