हमें एक स्ट्रिंग और एक रेंज दी गई है जो start से शुरू होकर end तक जाती है और कार्य दी गई रेंज में मौजूद पैलिंड्रोमिक सबस्ट्रिंग की गिनती करना है। पैलिंड्रोम स्ट्रिंग वे स्ट्रिंग हैं जो स्ट्रिंग के आगे और पीछे से समान होती हैं जैसे नितिन, aba, आदि।
उदाहरण के लिए
इनपुट - InputString = "cccaabbbdee", start = 2, end = 6;
आउटपुट - इंडेक्स रेंज में पैलिंड्रोमिक सबस्ट्रिंग की संख्या 7
व्याख्या - हमें एक रेंज और एक स्ट्रिंग दी गई है तो, हम स्ट्रिंग को start पॉइंट से पार करना शुरू करेंगे जो 2 है यानी 'c' तक 6 यानी 'b' इसलिए सबस्ट्रिंग 'caabb' है। तो पैलिंड्रोमिक सबस्ट्रिंग 'c', 'a', 'a', 'b' , 'b', 'aa' और 'bb' हैं। तो, पैलिंड्रोमिक सबस्ट्रिंग की संख्या 7 है।
इनपुट - InputString = "lioaabbbdee", start = 0, end = 2;
आउटपुट - इंडेक्स रेंज में पैलिंड्रोमिक सबस्ट्रिंग की संख्या 3
व्याख्या - हमें एक रेंज और एक स्ट्रिंग दी गई है तो, हम स्ट्रिंग को start पॉइंट से पार करना शुरू करेंगे जो 0 है यानी 'l' तक 2 यानी 'o' इसलिए सबस्ट्रिंग 'lio' है। तो पैलिंड्रोमिक सबस्ट्रिंग 'l', 'i' और 'o' हैं। तो, पैलिंड्रोमिक सबस्ट्रिंग की संख्या 3 है।
नीचे दिए गए प्रोग्राम में उपयोग किया गया दृष्टिकोण
- किसी भी दिए गए आकार की एक स्ट्रिंग घोषित करें और एक रेंज जो वेरिएबल start से शुरू होकर end तक जाती है।
- आगे की प्रोसेसिंग के लिए डेटा को palindrome_index(arr, InputString) नामक फ़ंक्शन में पास करें
- फ़ंक्शन के अंदर, सरणी आकार के साथ checked नामक एक और सरणी घोषित करें।
- सरणी की लंबाई तक i से 0 तक FOR लूप शुरू करें
- लूप के अंदर, सरणी की लंबाई तक j से 0 तक एक और FOR लूप शुरू करें
- लूप के अंदर, check को check[i][j] = 0 और arr[i][j] = 0 सेट करें
- length - 1 से i 0 से अधिक तक FOR लूप शुरू करें
- लूप के अंदर, check और arr को i के लिए 1 सेट करें फिर j से i + 1 तक सरणी की लंबाई तक एक और FOR लूप शुरू करें
- लूप के अंदर, चेक करें IF i पर स्ट्रिंग j पर स्ट्रिंग के बराबर है AND i + 1 j - 1 से बड़ा है OR 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]
- स्टार्ट और एंड के रूप में 2-D सरणी प्रिंट करें।
उदाहरण
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; 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
