हमें एक स्ट्रिंग इनपुट के रूप में दी गई है, कार्य दी गई इनपुट स्ट्रिंग के नॉन-ओवरलैपिंग पैलिंड्रोमिक सबस्ट्रिंग के जोड़े की संख्या ढूंढना है। arr[i][j] का मान सच है यदि सबस्ट्रिंग पैलिंड्रोम है, अन्यथा गलत। हम स्ट्रिंग से संयोजन लेंगे और जांचेंगे कि क्या जोड़े मानदंडों को पूरा करते हैं।
उदाहरणों से समझते हैं।
इनपुट: ABC
आउटपुट: नॉन-ओवरलैपिंग पैलिंड्रोमिक सबस्ट्रिंग जोड़े की संख्या 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(text) में पास किया जाता है।
- प्रारंभ में आकार 100 का एक बूलियन 2D सरणी arr[ ][ ] बनाई जाती है और बॉटम-अप दृष्टिकोण में भरने के लिए बनाए रखा जाता है और इनपुट स्ट्रिंग (text) को वर्ण सरणी में परिवर्तित किया जाता है।
- सरणी की गणना तब arr[i+1][j-1] के मान की जांच करके की जाती है, यदि मान सच है और str[i] str[j] के समान है, तो हम arr[i][j] को सच बनाते हैं। अन्यथा, arr[i][j] का मान गलत बनाया जाता है।
- उसके बाद start[ ] और end[ ] इनिशियलाइज़ किए जाते हैं और start[i] इंडेक्स के बाईं ओर के पैलिंड्रोम की संख्या संग्रहीत करता है (i सहित) और end[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