লংগেস্ট প্যালিনড্রোমিক সাবসিকোয়েন্স (Longest Palindromic Subsequence) বের করার জাভা কোড নিচে দেওয়া হলো:
উদাহরণ
public class Demo{
static String longest_seq(String str_1, String str_2){
int str_1_len = str_1.length();
int str_2_len = str_2.length();
char str_1_arr[] = str_1.toCharArray();
char str_2_arr[] = str_2.toCharArray();
int L[][] = new int[str_1_len + 1][str_2_len + 1];
for (int i = 0; i <= str_1_len; i++){
for (int j = 0; j <= str_2_len; j++){
if (i == 0 || j == 0){
L[i][j] = 0;
}
else if (str_1_arr[i - 1] == str_2_arr[j - 1]){
L[i][j] = L[i - 1][j - 1] + 1;
}
else{
L[i][j] = Math.max(L[i - 1][j], L[i][j - 1]);
}
}
}
int my_index = L[str_1_len][str_2_len];
char[] longest_seq = new char[my_index + 1];
int i = str_1_len, j = str_2_len;
while (i > 0 && j > 0){
if (str_1_arr[i - 1] == str_2_arr[j - 1]){
longest_seq[my_index - 1] = str_1_arr[i - 1];
i--;
j--;
my_index--;
}
else if (L[i - 1][j] > L[i][j - 1]){
i--;
} else {
j--;
}
}
String my_result = "";
for (int x = 0; x < longest_seq.length; x++){
my_result += longest_seq[x];
}
return my_result;
}
static String longestPalSubseq(String str){
String rev_str = str;
rev_str = reverse_str(rev_str);
return longest_seq(str, rev_str);
}
static String reverse_str(String str){
String my_result = "";
char[] trial = str.toCharArray();
for (int i = trial.length - 1; i >= 0; i--){
my_result += trial[i];
}
return my_result;
}
public static void main(String[] args){
String str = "HelloHelloo";
System.out.println("Longest palindromic subsequence is ");
System.out.println(longestPalSubseq(str));
}
}
আউটপুট
Longest palindromic subsequence is llell
Demo নামে একটি ক্লাস আছে যেটিতে 'longest_seq' ফাংশন আছে যা দুটি স্ট্রিং এবং দুটি ক্যারেক্টার অ্যারে ডিক্লেয়ার করে। অ্যারেগুলো ইটারেট করে, ডাইনামিক প্রোগ্রামিং টেকনিক ব্যবহার করে লংগেস্ট প্যালিনড্রোমিক সিকোয়েন্স বের করা হয়। এই মেথডে, একবার কোনো স্পেসিফিক অ্যারের জন্য মান পাওয়া যাওয়ায়, সেটি স্টোর করা হয় এবং পুনরায় কম্পিউট করা হয় না, যাতে ক্যালকুলেশন এফিশিয়েন্ট হয়।
'longestPalSubseq' নামে একটি ফাংশন স্ট্রিং প্যারামিটার হিসেবে নেয়, স্ট্রিংটি রিভার্স করে 'longest_seq' ফাংশন কল করে রিভার্সড স্ট্রিং পাস করে। 'reverse_str' নামে আর একটি ফাংশন স্ট্রিং রিভার্স করতে ব্যবহৃত হয়। main ফাংশনে স্ট্রিং ডিফাইন করা হয়, এবং 'longestPalSubseq' ফাংশন কল করা হয়, আউটপুট কনসোলে প্রদর্শিত হয়।
