আমাদেরকে একটি স্ট্রিং হিসাবে একটি ইনপুট দেওয়া হয়েছে, কাজটি হল প্রদত্ত ইনপুট স্ট্রিং-এর নন-ওভারল্যাপিং প্যালিনড্রোমিক সাব-স্ট্রিংগুলির জোড়ার সংখ্যা বের করা। arr[i][j] এর মান সত্য হয় যদি সাবস্ট্রিং একটি প্যালিনড্রোম হয়, অন্যথায় মিথ্যা। আমরা স্ট্রিং থেকে সংমিশ্রণ বের করব এবং জোড়াগুলি মানদণ্ড পূরণ করে কিনা তা পরীক্ষা করব।
আসুন উদাহরণ দিয়ে বোঝা যাক।
ইনপুট: এবিসি
আউটপুট: নন-ওভারল্যাপিং প্যালিনড্রোমিক সাব-স্ট্রিংগুলির জোড়া গণনা হল 3
ব্যাখ্যা: সম্ভাব্য জোড়া হল (A) (B) (C), (A) (BC), (AB) (C), (ABC)
ইনপুট: ABCD
আউটপুট: নন-ওভারল্যাপিং প্যালিনড্রোমিক সাব-স্ট্রিংগুলির জোড়া গণনা হল 8
ব্যাখ্যা: সম্ভাব্য জোড়া হল (A)(B)(C)(D),(A)(B)(CD),(A)(BC)(D),(A)(BCD),(AB)(C) (D),(AB)(CD),
(ABC)(D), (ABCD)
নিম্নলিখিত প্রোগ্রামে ব্যবহৃত পদ্ধতি
- একটি স্ট্রিং ইনপুট হিসাবে নেওয়া হয় এবং আরও প্রক্রিয়াকরণের জন্য ফাংশন pair_count(টেক্সট) এ পাস করা হয়।
- প্রাথমিকভাবে 100 arr[ ][ ] আকারের একটি বুলিয়ান 2D অ্যারে তৈরি করা হয় এবং রক্ষণাবেক্ষণ করা হয় যাতে একটি নিচের দিকের পদ্ধতিতে পূরণ করা হয় এবং ইনপুট স্ট্রিং (টেক্সট) একটি অক্ষর অ্যারেতে রূপান্তরিত হয়।
- অতঃপর অ্যারেটি গণনা করা হয় arr[i+1][j-1] মান পরীক্ষা করে, যদি মান সত্য হয় এবং str[i] str[j] এর মতো হয়, তাহলে আমরা arr[i] করি [j] সত্য। অন্যথায়, arr[i][j] এর মান মিথ্যা করা হয়।
- তার পর শুরু[ ] এবং শেষ[ ] শুরু করা হয় এবং স্টার্ট[i] সূচকের বাম দিকে প্যালিনড্রোম সংখ্যার প্যালিনড্রোম গণনা সংরক্ষণ করে (i সহ) এবং শেষ [i] সংখ্যার প্যালিনড্রোম গণনা সংরক্ষণ করে সূচকের ডানদিকে উপাদানগুলির (i সহ)
- একটি লুপ 0 থেকে str.length() - 1 পর্যন্ত পুনরাবৃত্তি করা হয় এবং লুপের ভিতরে ফলাফলটি start[i] * end[i + 1] এর গুণফলের সাথে যোগ করে ফলাফল গণনা করা হয়।
উদাহরণ
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); //ABCD
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
