একটি ইনপুট স্ট্রিং দেওয়া আছে। কাজ হল ওই স্ট্রিংয়ের নন-ওভারল্যাপিং প্যালিনড্রোমিক সাবস্ট্রিং পেয়ারের সংখ্যা বের করা। arr[i][j] হবে true যদি সাবস্ট্রিংটি প্যালিনড্রোম হয়, অন্যথায় false। স্ট্রিংয়ের কোম্বিনেশন বের করে চেক করা হবে পেয়ারগুলো শর্ত পূরণ করে কিনা।
উদাহরণ দিয়ে বোঝা যাক
ইনপুট: ABC
আউটপুট: নন-ওভারল্যাপিং প্যালিনড্রোমিক সাবস্ট্রিং পেয়ারের সংখ্যা ৩
ব্যাখ্যা: সম্ভাব্য পেয়ারগুলো: (A)(B)(C), (A)(BC), (AB)(C), (ABC)
ইনপুট: ABCD
আউটপুট: নন-ওভারল্যাপিং প্যালিনড্রোমিক সাবস্ট্রিং পেয়ারের সংখ্যা ৮
ব্যাখ্যা: সম্ভাব্য পেয়ারগুলো: (A)(B)(C)(D), (A)(B)(CD), (A)(BC)(D), (A)(BCD), (AB)(C)(D), (AB)(CD), (ABC)(D), (ABCD)
প্রোগ্রামে ব্যবহৃত পদ্ধতি
- স্ট্রিং ইনপুট নিয়ে
pair_count(text)ফাংশনে পাস করুন। - বুলিয়ান ২ডি অ্যারে
arr[100][100]বটম-আপ পদ্ধতিতে পূরণ করুন এবং স্ট্রিংকে ক্যারেক্টার অ্যারেতে কনভার্ট করুন। - অ্যারে ক্যালকুলেট করুন:
arr[i+1][j-1]চেক করে। যদি true হয় এবংstr[i]==str[j]হয় তবেarr[i][j]=true, অন্যথায় false। start[]এবংend[]ইনিশিয়ালাইজ করুন।start[i]= বাম পাশের প্যালিনড্রোম কাউন্ট (i সহ)।end[i]= ডান পাশের প্যালিনড্রোম কাউন্ট (i সহ)।- i=0 থেকে str.length()-1 পর্যন্ত লুপে রেজাল্টে
start[i] * end[i+1]যোগ করুন।
উদাহরণ কোড (Java)
import java.io.*;
import java.util.*;
class tutorialPoint {
static int SIZE = 100;
static int pair_count(String str) {
boolean arr[][] = new boolean[SIZE][SIZE];
char[] ch = str.toCharArray();
for (int i = 0; i < ch.length; i++) {
for (int j = 0; j < ch.length; j++) {
arr[i][j] = false;
}
}
for (int j = 1; j <= ch.length; j++) {
for (int i = 0; i <= ch.length - j; i++) {
if (j <= 2) {
if (ch[i] == ch[i + j - 1]) {
arr[i][i + j - 1] = true;
}
} else if (ch[i] == ch[i + j - 1]) {
arr[i][i + j - 1] = arr[i + 1][i + j - 2];
}
}
}
int start[] = new int[str.length()];
int end[] = new int[str.length()];
start[0] = 1;
for (int i = 1; i < str.length(); i++) {
for (int j = 0; j <= i; j++) {
if (arr[j][i] == true) start[i]++;
}
}
end[str.length() - 1] = 1;
for (int i = str.length() - 2; i >= 0; i--) {
end[i] = end[i + 1];
for (int j = str.length() - 1; j >= i; j--) {
if (arr[i][j] == true) end[i]++;
}
}
int result = 0;
for (int i = 0; i < str.length() - 1; i++) {
result = result + start[i] * end[i + 1];
}
return result;
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
String text = scan.next();
System.out.println("Count pairs of non-overlapping palindromic sub-strings is\t" + pair_count(text));
}
}
উপরের কোড রান করলে নিচের আউটপুটটি পাওয়া যাবে:
আউটপুট
Count pairs of non-overlapping palindromic sub-strings is 8
