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

একটি প্রদত্ত স্ট্রিংসে, আমাদের এমন একটি সাবস্ট্রিং খুঁজে বের করতে হবে যা প্যালিনড্রোম এবং দৈর্ঘ্য দি೟ে সর্বোচ্চ।

সর্বোচ্চ দৈর্ঘ্যের প্যালিনড্রোমিক সাবস্ট্রিং পেতে হলে অনেক উপসমস্যা সমাধান করতে হয়, जिनमें কিছু ওভারল্যাপ করে। একই উপসমস্যা বারবার সমাধান না করে ডাইনামিক প্রোগ্রামিং ব্যবহার করে একটি টেবিলে পূর্বের ফলাফল সংরক্ষণ করা হয় এবং পরবর্তী ফলাফল তৈরি করা হয়।

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

ইনপুট: একটি স্ট্রিং। যেমন "thisispalapsiti"
আউটপুট: প্যালিনড্রোম সাবস্ট্রিং এবং এর দৈর্ঘ্য।
সর্বোচ্চ প্যালিনড্রোম সাবস্ট্রিং: ispalapsi
দৈর্ঘ্য: ৯

অ্যালগরিদম

findLongPalSubstr(str)

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

শুরু
  n := প্রদত্ত স্ট্রিংর দৈর্ঘ্য
  palTab নামক n x n টেবিল তৈরি করুন true/false মান সংরক্ষণের জন্য
  patTab কে false মান দিয়ে পূরণ করুন
  maxLen := 1
  i := 0 থেকে n-1 পর্যন্ত, করুন
    palTab[i, i] = true  // দৈর্ঘ্য ১ এর প্যালিনড্রোম
  শেষ
  start := 0
  i := 0 থেকে n-2 পর্যন্ত, করুন
    যদি str[i] = str[i+1] হয়, তবে
      palTab[i, i+1] := true
      start := i
      maxLen := 2
  শেষ
  k := 3 থেকে n পর্যন্ত, করুন
    i := 0 থেকে n-k পর্যন্ত, করুন
      j := i + k - 1
      যদি palTab[i+1, j-1] এবং str[i] = str[j] হয়, তবে
        palTab[i, j] := true
        যদি k > maxLen হয়, তবে
          start := i
          maxLen := k
    শেষ
  শেষ
  str থেকে start থেকে maxLen দৈর্ঘ্যের সাবস্ট্রিং প্রদর্শন করুন এবং maxLen ফেরত দিন
শেষ

উদাহরণ (C++)

#include <iostream>
using namespace std;

int findLongPalSubstr(string str) {
  int n = str.size();
  bool palCheckTab[n][n];
  for(int i = 0; i < n; i++)
    for(int j = 0; j < n; j++)
      palCheckTab[i][j] = false;

  int maxLength = 1;
  for (int i = 0; i < n; ++i)
    palCheckTab[i][i] = true;

  int start = 0;
  for (int i = 0; i < n-1; ++i) {
    if (str[i] == str[i+1]) {
      palCheckTab[i][i+1] = true;
      start = i;
      maxLength = 2;
    }
  }

  for (int k = 3; k <= n; ++k) {
    for (int i = 0; i < n-k+1; ++i) {
      int j = i + k - 1;
      if (palCheckTab[i+1][j-1] && str[i] == str[j]) {
        palCheckTab[i][j] = true;
        if (k > maxLength) {
          start = i;
          maxLength = k;
        }
      }
    }
  }

  cout << "Longest palindrome substring is: " << str.substr(start, maxLength) << endl;
  return maxLength;
}

int main() {
  char str[] = "thisispalapsiti";
  cout << "Length is: " << findLongPalSubstr(str);
}

আউটপুট

Longest palindrome substring is: ispalapsi
Length is: 9