একটি স্ট্রিং এবং একটি রেঞ্জ start থেকে end দেওয়া আছে। কাজ হল সেই রেঞ্জে থাকা প্যালিনড্রোমিক সাবস্ট্রিংর সংখ্যা বের করা। প্যালিনড্রোম স্ট্রিং হলো যেটি সামনে থেকে ও পিছনে থেকে পড়লে একই (যেমন: nitin, aba)।
উদাহরণ
ইনপুট - InputString = "cccaabbbdee", start = 2, end = 6
আউটপুট - ইনডেক্স রেঞ্জে প্যালিনড্রোমিক সাবস্ট্রিং সংখ্যা: ৭
ব্যাখ্যা - রেঞ্জ ২ থেকে ৬ অর্থাৎ সাবস্ট্রিং "caabb"। প্যালিনড্রোমিক সাবস্ট্রিং: 'c', 'a', 'a', 'b', 'b', 'aa', 'bb' — মোট ৭টি।
ইনপুট - InputString = "lioaabbbdee", start = 0, end = 2
আউটপুট - ইনডেক্স রেঞ্জে প্যালিনড্রোমিক সাবস্ট্রিং সংখ্যা: ৩
ব্যাখ্যা - রেঞ্জ ০ থেকে ২ অর্থাৎ সাবস্ট্রিং "lio"। প্যালিনড্রোমিক সাবস্ট্রিং: 'l', 'i', 'o' — মোট ৩টি।
প্রোগ্রামে ব্যবহৃত পদ্ধতি
- স্ট্রিং এবং রেঞ্জ ডিক্লেয়ার করুন।
palindrome_index(arr, InputString)ফাংশনে পাস করুন।- ফাংশন ভিতরে
checkedঅ্যারে ডিক্লেয়ার করুন। - i=0 থেকে length পর্যন্ত FOR লুপ, ভিতরে j=0 থেকে length পর্যন্ত FOR লুপ:
check[i][j]=0, arr[i][j]=0। - i=length-1 থেকে ০ পর্যন্ত লুপ:
check[i][i]=arr[i][i]=1। j=i+1 থেকে length-১ পর্যন্ত লুপ: যদিs[i]==s[j] && (i+1>j-1 || check[i+1][j-1]!=0)হয় তবেcheck[i][j]=1, অন্যথায় ০।arr[i][j] = arr[i][j-1] + arr[i+1][j] - arr[i+1][j-1] + check[i][j]। - ২ডি অ্যারে
arr[start][end]প্রিন্ট করুন।
উদাহরণ কোড (Java)
import java.io.*;
class testqwe {
static void palindrome_index(int arr[][], String s) {
int length = s.length();
int[][] check = new int[length + 1][length + 1];
for (int i = 0; i <= length; i++) {
for (int j = 0; j <= length; j++) {
check[i][j] = 0;
arr[i][j] = 0;
}
}
for (int i = length - 1; i >= 0; i--) {
check[i][i] = arr[i][i] = 1;
for (int j = i + 1; j < length; j++) {
if (s.charAt(i) == s.charAt(j) && (i + 1 > j - 1 || check[i + 1][j - 1] != 0)) {
check[i][j] = 1;
} else {
check[i][j] = 0;
}
arr[i][j] = arr[i][j - 1] + arr[i + 1][j] - arr[i + 1][j - 1] + check[i][j];
}
}
}
public static void main(String args[]) {
String InputString = "cccaabbbdee";
int[][] arr = new int[50][50];
palindrome_index(arr, InputString);
int start = 2;
int end = 6;
System.out.println("Count of Palindromic substrings in an Index range " + arr[start][end]);
}
}
উপরের কোড রান করলে নিচের আউটপুটটি পাওয়া যাবে:
আউটপুট
Count of Palindromic substrings in an Index range 7
