Palindrome tree
कंप्यूटर विज्ञान में एक पालिंड्रोम वृक्ष, जिसे एर्ट्री भी कहा जाता है, एक प्रकार का खोज वृक्ष है, जो एक स्ट्रिंग में निहित सभी पालिंड्रोम तक तेजी से पहुंच की अनुमति देता है। इनका उपयोग सबसे लंबे पालिंड्रोमिक सबस्ट्रिंग, के-फैक्टराइजेशन समस्या (क्या किसी दिए गए स्ट्रिंग को बिल्कुल के पालिंड्रोम्स में विभाजित किया जा सकता है), एक स्ट्रिंग की पालिंड्रोमिक लंबाई (स्ट्रिंग के निर्माण के लिए आवश्यक पालिंड्रोम्स की न्यूनतम संख्या क्या है), और सभी अलग-अलग उप-पालिंड्रोम्स को खोजने और गिनने के लिए किया जा सकता है। पालिंड्रोम पेड़ इसे ऑनलाइन तरीके से करते हैं, यानी इसे शुरुआत में पूरे तार की आवश्यकता नहीं होती है और इसे चरित्र द्वारा वर्ण में जोड़ा जा सकता है। विवरण अधिकांश पेड़ों की तरह, एक पालिंड्रोम पेड़ में शीर्ष और निर्देशित किनारे होते हैं। पेड़ में प्रत्येक शीर्ष एक पालिंड्रोम का प्रतिनिधित्व करता है (जैसे। 'टैकोकट') लेकिन केवल पालिंड्रोम की लंबाई को संग्रहीत करता है, और प्रत्येक किनारा या तो एक वर्ण या प्रत्यय का प्रतिनिधित्व करता है। वर्ण के किनारे यह दर्शाते हैं कि जब वर्ण को स्रोत शीर्ष द्वारा दर्शाए गए पालिंड्रोम के दोनों सिरों पर जोड़ा जाता है, तो गंतव्य शीर्ष में पालिंड्रोम बनाया जाता है (जैसे। 'टी' लेबल वाला एक किनारा स्रोत शीर्ष 'एकोका' को गंतव्य शीर्ष 'टैकोकेट' से जोड़ेगा)। प्रत्यय किनारा प्रत्येक पालिंड्रोम को उसके पास मौजूद सबसे बड़े पालिंड्रोम प्रत्यय से जोड़ता है (पिछले उदाहरण में 'टैकोकट' का प्रत्यय किनारा 'टी' होगा, और 'अटाकोकाटा' का प्रत्यय लिंक 'अता' होगा)। जहां पालिंड्रोम के पेड़ नियमित पेड़ों से अलग होते हैं, वह यह है कि उनकी दो जड़ें होती हैं (क्योंकि वे वास्तव में दो अलग-अलग पेड़ हैं)। दोनों जड़ें −1, और 0 लंबाई के पालिंड्रोम्स का प्रतिनिधित्व करती हैं। अर्थात्, यदि अक्षर 'ए' को दोनों जड़ों से जोड़ा जाता है तो पेड़ क्रमशः 'ए' और 'आ' उत्पन्न करेगा। चूँकि प्रत्येक किनारा वर्णों की एक सम संख्या जोड़ता है (या हटा देता है), दोनों पेड़ हमेशा केवल प्रत्यय किनारों से जुड़े रहते हैं। चूंकि एक पालिंड्रोम पेड़ एक ऑनलाइन निर्माण का अनुसरण करता है, इसलिए यह पेड़ में जोड़े गए अंतिम पालिंड्रोम के लिए एक सूचक रखता है। पैलिन्ड्रोम वृक्ष में अगले वर्ण को जोड़ने के लिए, जोड़ें (x) पहले जाँच करता है कि क्या पैलिन्ड्रोम से पहले का पहला वर्ण जोड़े जा रहे वर्ण से मेल खाता है, यदि ऐसा नहीं होता है, तो प्रत्यय लिंक का पालन तब तक किया जाता है जब तक कि वृक्ष में एक पैलिन्ड्रोम नहीं जोड़ा जा सकता है। एक बार जब एक पालिंड्रोम मिल जाता है, अगर यह पहले से ही पेड़ में मौजूद है, तो कोई काम नहीं है। अन्यथा, प्रत्यय से नए शीर्ष तक एक कड़ी के साथ एक नया शीर्ष जोड़ा जाता है, और नए शीर्ष के लिए एक प्रत्यय कड़ी जोड़ी जाती है। यदि नए पालिंड्रोम की लंबाई 1 है, तो प्रत्यय लिंक पालिंड्रोम पेड़ की जड़ की ओर इशारा करता है जो-1 की लंबाई का प्रतिनिधित्व करता है। #एस-> इनपुट स्ट्रिंग #एक्स-> वर्ण की स्ट्रिंग में स्थिति जिसे जोड़ा जा रहा है डेफ ऐड (एक्सः इंट)-> बूलः "" पालिंड्रोम ट्री में वर्ण जोड़ें ""। जबकि सचः यदि x-1-current.length> = 0 और S [x-1-current.length] = = S [x]: ब्रेक करंट = current.suffix यदि current.add [S [x] कोई नहीं हैः लौटें गलत प्रत्यय = वर्तमान करंट = पैलिन्ड्रोम _ वर्टेक्स () current.length = suffix.length + 2 suffix.add [S [x] = वर्तमान यदि current.length = = 1: current.suffix = रूट रिटर्न सही जबकि सचः प्रत्यय = suffix.suffix यदि x-1-suffix.length = 0 और S [x-suffix.length = = S [x]: current.suffix यह प्रत्येक शीर्ष में लंबाई की एक सरणी जोड़कर, और सूचकांक पर ध्वज को 1 पर सेट करके पूरा किया जाता है यदि स्ट्रिंग जोड़ते समय उस शीर्ष तक पहुँच गया था। एकमात्र अन्य संशोधन की आवश्यकता वर्तमान सूचक को प्रत्येक स्ट्रिंग के अंत में रूट पर रीसेट करना है। पेड़ों को इस तरह से जोड़ने से निम्नलिखित समस्याओं का समाधान किया जा सकता हैः सभी तारों के लिए सामान्य पालिंड्रोम की संख्या एक तार में अद्वितीय पालिंड्रोम की संख्या सभी तारों के लिए सबसे लंबा पालिंड्रोम पालिंड्रोम की संख्या जो एक तार में दूसरों की तुलना में अधिक बार होती है एक पालिंड्रोम पेड़ के निर्माण में समय लगता है, जहां तार की लंबाई और वर्णमाला का आकार होता है। (x) जोड़ने के लिए कॉल के साथ, प्रत्येक कॉल में परिशोधन समय लगता है। यह जोड़ने के लिए प्रत्येक कॉल का परिणाम है (x) वर्तमान शीर्ष (पेड़ में अंतिम पालिंड्रोम) की गहराई को अधिक से अधिक एक से बढ़ाता है, और एक शीर्ष के सभी संभावित वर्ण किनारों को खोजने में समय लगता है। (x) जोड़ने के लिए प्रत्येक कॉल के लिए पेड़ को ऊपर और नीचे ले जाने की लागत निर्धारित करने से, पेड़ को ऊपर ले जाने पर (x) जोड़ने के लिए समान संख्या में कॉल द्वारा एक से अधिक बार पेड़ को ऊपर ले जाने की लागत का 'भुगतान' किया जाता है। एक पालिंड्रोम वृक्ष स्थान लेता हैः अधिकांश शीर्षों पर उप-पालिंड्रोम और दो जड़ों, किनारों को संग्रहीत करने के लिए, शीर्षों और प्रत्यय किनारों को जोड़ता है। यदि प्रत्येक पालिंड्रोम के लिए मौजूद केवल जोड़ किनारों को संग्रहीत करने के बजाय लंबाई के किनारों की एक सरणी संग्रहीत की जाती है, तो सही किनारे का पता लगाने के लिए निर्माण समय को कम करने के लिए निरंतर समय में किया जा सकता है, जबकि जगह को बढ़ाते हुए, पालिंड्रोम की संख्या कहाँ है। संदर्भ वृक्ष (डेटा संरचना)