দীর্ঘতম প্যালিনড্রোমিক সাবস্ট্রিং

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

দীর্ঘতম প্যালিনড্রোমিক সাবস্ট্রিং পেতে, আমাদের অনেকগুলি সাব-সমস্যা সমাধান করতে হবে, কিছু সাব-প্রবলেম ওভারল্যাপ হচ্ছে। তাদের একাধিকবার সমাধান করা প্রয়োজন। যে কারণে, ডায়নামিক প্রোগ্রামিং সহায়ক। একটি টেবিল ব্যবহার করে, আমরা পূর্ববর্তী উপ-সমস্যাগুলির ফলাফল সংরক্ষণ করতে পারি, এবং আরও ফলাফল তৈরি করতে ব্যবহার করতে পারি৷

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

ইনপুট:একটি স্ট্রিং। বলুন “thisispalapsiti”আউটপুট:প্যালিনড্রোম সাবস্ট্রিং এবং প্যালিনড্রোমের দৈর্ঘ্য। দীর্ঘতম প্যালিনড্রোম সাবস্ট্রিং হল:ইসপালাপসি দৈর্ঘ্য হল:9

অ্যালগরিদম

findLongPalSubstr(str)

ইনপুট - প্রধান স্ট্রিং।

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

শুরু করুন n :=প্রদত্ত স্ট্রিংটির দৈর্ঘ্য palTab নামে anxn টেবিল তৈরি করুন যাতে সত্য বা মিথ্যা মান patTab-কে মিথ্যা মান দিয়ে পূরণ করুন maxLen :=1 for i :=0 থেকে n-1, করুন patTab[i, i] =সত্য //যেহেতু এটি দৈর্ঘ্যের প্যালিনড্রোম 1 সম্পন্ন হয়েছে :=0 এর জন্য i :=0 থেকে n-2, যদি str[i] =str[i-1] হয়, তাহলে palTab[i, i+1] :=true start :=i maxLen :=2 করা হয়েছে k :=3 থেকে n এর জন্য, do for i :=0 থেকে nk, do j :=i + k – 1 যদি palTab[i+1, j-1] এবং str[ i] =str[j], তারপর palTab[i, j] :=সত্য হলে k> maxLen, তারপর শুরু করুন :=i maxLen :=k সম্পন্ন হয়েছে ডিসপ্লে সাবস্ট্রিং শুরু থেকে str থেকে maxLen পর্যন্ত, এবং maxLen End ফেরত দিন।> 
উদাহরণ
 
#include namespace ব্যবহার করে std;int findLongPalSubstr(string str) { int n =str.size(); // ইনপুট স্ট্রিং বুলের দৈর্ঘ্য পান palCheckTab[n][n]; //সত্য যখন i থেকে j পর্যন্ত সাবস্ট্রিং হয় তখন প্যালিনড্রোম হয় (int i =0; i সর্বোচ্চ দৈর্ঘ্য) { শুরু =i; maxLength =k; } } } } cout <<"দীর্ঘতম প্যালিনড্রোম সাবস্ট্রিং হল:" < 
আউটপুট
 
দীর্ঘতম প্যালিনড্রোম সাবস্ট্রিং হল:ispalapsi দৈর্ঘ্য হল:9