সর্বোচ্চ দৈর্ঘ্যের প্যালিনড্রোমিক সাবসিকোয়েন্স

সর্বোচ্চ প্যালিনড্রোমিক সাবসিকোয়েন্স হল একটি প্রদত্ত সিকোয়েন্সের সাবসিকোয়েন্স, যা প্যালিনড্রোম।

এই সমস্যায় একটি ক্যারেক্টার সিকোয়েন্স দেওয়া থাকে, আমাদের প্যালিনড্রোমিক সাবসিকোয়েন্সের সর্বোচ্চ দৈর্ঘ্য বের করতে হবে।

এই সমস্যা সমাধানের জন্য রিকার্সিভ সূত্র ব্যবহার করা যায়:

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

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

ইনপুট: ভিন্ন অক্ষর বা চিহ্ন সহ একটি স্ট্রিং। ধরা যাক ইনপুট "ABCDEEAB"
আউটপুট: সর্বোচ্চ প্যালিনড্রোমিক সাবসিকোয়েন্সের দৈর্ঘ্য। এখানে এটি ৪।
ABCDEEAB। তাই প্যালিনড্রোম হল AEEA।

অ্যালগরিদম

palSubSeqLen(str)

ইনপুট: প্রদত্ত স্ট্রিং।
আউটপুট: সর্বোচ্চ প্যালিনড্রোমিক সাবসিকোয়েন্সের দৈর্ঘ্য।

শুরু
  n = স্ট্রিংর দৈর্ঘ্য
  n x n আকারের lenTable নামক টেবিল তৈরি করুন এবং ১ দিয়ে পূরণ করুন
  col := 2 থেকে n পর্যন্ত, করুন
    i := 0 থেকে n-col পর্যন্ত, করুন
      j := i + col - 1
      যদি str[i] = str[j] এবং col = 2 হয়, তবে
        lenTable[i, j] := 2
      অন্যথায় যদি str[i] = str[j] হয়, তবে
        lenTable[i, j] := lenTable[i+1, j-1] + 2
      অন্যথায়
        lenTable[i, j] := lenTable[i, j-1] এবং lenTable[i+1, j] এর মধ্যে সর্বোচ্চ
    শেষ
  শেষ
  lenTable[0, n-1] ফেরত দিন
শেষ

উদাহরণ (C++)

#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];
  for (int i = 0; i < n; i++)
    lenTable[i][i] = 1;
  for (int col=2; col<=n; col++) {
    for (int i=0; i

আউটপুট
The length of the longest palindrome subsequence is: 4