এই অ্যালগরিদমে ইনপুট একটি স্ট্রিং। স্ট্রিংটির একটি পার্টিশনিংকে প্যালিনড্রোম পার্টিশনিং বলা হয় যখন পার্টিশনের প্রতিটি সাবস্ট্রিং প্যালিনড্রোম হয়।
এই অ্যালগরিদমে প্রদত্ত স্ট্রিং-কে প্যালিনড্রোম পার্টিশন করার জন্য ন্যূনতম কতটি কাট (cut) প্রয়োজন তা বের করতে হবে।
ইনপুট এবং আউটপুট
ইনপুট: একটি স্ট্রিং। যেমন "ababbbabbababa" আউটপুট: প্যালিনড্রোম পার্টিশন করার জন্য ন্যূনতম কাট। এখানে ৩টি কাট প্রয়োজন। প্যালিনড্রোমগুলো: a | babbbab | b | ababa
অ্যালগরিদম
minPalPart(str)
ইনপুট: প্রদত্ত স্ট্রিং।
আউটপুট: স্ট্রিং থেকে প্যালিনড্রোমিক পার্টিশনিং-এর ন্যূনতম সংখ্যা।
শুরু
n := str-এর দৈর্ঘ্য
n x n ক্রমের cut এবং pal ম্যাট্রিক্স সংজ্ঞায়িত করুন
i := 0 থেকে n পর্যন্ত, করুন
pal[i, i] := true
cut[i, i] := 0
শেষ
len := 2 থেকে n পর্যন্ত রেঞ্জে, করুন
i := 0 থেকে n-len পর্যন্ত রেঞ্জে, করুন
j := i + len - 1
যদি len = 2 হয়, তবে
যদি str[i] = str[j] হয়, তবে
pal[i, j] := true
অন্যথায়
যদি str[i] = str[j] এবং pal[i+1, j-1] ≠ 0 হয়, তবে
pal[i, j] := true
যদি pal[i, j] সত্য হয়, তবে
cut[i, j] := 0
অন্যথায়
cut[i, j] := ∞
k := i থেকে j-1 পর্যন্ত, করুন
cut[i, j] := cut[i, j] এবং (cut[i, k] + cut[k+1, j] + 1) এর মধ্যে ন্যূনতম
শেষ
শেষ
শেষ
cut[0, n-1] ফেরত দিন
শেষ
উদাহরণ (C++)
#include <iostream>
using namespace std;
int min(int a, int b) { return (a < b) ? a : b; }
int minPalPartion(string str) {
int n = str.size();
int cut[n][n];
bool pal[n][n];
for (int i=0; i
আউটপুট
Min cuts for Palindrome Partitioning is: 3
