দীর্ঘতম প্যালিনড্রোমিক অনুবর্তন

দীর্ঘতম প্যালিনড্রোমিক সাবসিক্যুয়েন্স হল একটি প্রদত্ত সিকোয়েন্সের পরের অংশ এবং পরবর্তীটি হল একটি প্যালিনড্রোম৷

এই সমস্যাটিতে, অক্ষরের একটি ক্রম দেওয়া হয়েছে, আমাদের একটি প্যালিনড্রোমিক অনুসারীর দীর্ঘতম দৈর্ঘ্য খুঁজে বের করতে হবে।

এই সমস্যা সমাধানের জন্য, আমরা পুনরাবৃত্তিমূলক সূত্র ব্যবহার করতে পারি,

যদি L (0, n-1) ব্যবহার করা হয় দীর্ঘতম প্যালিনড্রোমিক পরবর্তী দৈর্ঘ্য সংরক্ষণ করতে, তাহলে
L (0, n-1) :=L (1, n-2) + 2 (যখন 0'th এবং (n-1)'th অক্ষর একই হয়)।

ইনপুট এবং আউটপুট

Input:
A string with different letters or symbols. Say the input is “ABCDEEAB”
Output:
The longest length of the largest palindromic subsequence. Here it is 4.
ABCDEEAB. So the palindrome is AEEA.

অ্যালগরিদম

palSubSeqLen(str)

ইনপুট - প্রদত্ত স্ট্রিং।

আউটপুট - দীর্ঘতম প্যালিনড্রোমিক পরবর্তী দৈর্ঘ্য।

Begin
   n = length of the string
   create a table called lenTable of size n x n and fill with 1s
   for 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] := maximum of lenTable[i, j-1] and lenTable[i+1, j]
      done
   done
   return lenTable[0, n-1]
End

উদাহরণ

#include<iostream>
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];            // Create a table to store results of subproblems

   for (int i = 0; i < n; i++)
      lenTable[i][i] = 1;             //when string length is 1, it is palindrome

   for (int col=2; col<=n; col++) {
      for (int i=0; i<n-col+1; i++) {
         int j = i+col-1;
         if (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] = max(lenTable[i][j-1], lenTable[i+1][j]);
      }
   }
   return lenTable[0][n-1];
}

int main() {
   string sequence = "ABCDEEAB";
   int n = sequence.size();
   cout << "The length of the longest palindrome subsequence is: " << palSubseqLen(sequence);
}

আউটপুট

The length of the longest palindrome subsequence is: 4