बीओआर

Bor स्ट्रिंग्स के एक सेट को संग्रहीत करने के लिए एक डेटा संरचना है, जो कि किनारों पर प्रतीकों वाला एक जड़ वाला पेड़ है। < /दिवि>
प्रत्येक बोरॉन वर्टेक्स कुछ जोड़े गए स्ट्रिंग के उपसर्ग से मेल खाता है। यह उपसर्ग स्वयं जड़ से इस शीर्ष तक के मार्ग पर किनारों पर क्रमिक रूप से अक्षर लिखकर प्राप्त किया जाता है। उसी समय, ठीक एक शीर्ष प्रत्येक मौजूदा उपसर्ग से मेल खाता है। बोर रूट एक खाली स्ट्रिंग से मेल खाता है।

{be, bee, can, cat, cd
के लिए बोरॉन का उदाहरण


ऑरेंज उन शीर्षों को इंगित करता है जो स्वयं सेट से शब्दों के अनुरूप होते हैं। उन्हें टर्मिनल कहा जाता है।

नीचे बोरॉन को स्टोर करने और उसमें लाइन जोड़ने के लिए कोड है। यह विधि बोर को एक सरणी के माध्यम से संग्रहीत करती है। पॉइंटर्स के माध्यम से एक कार्यान्वयन भी है, जो प्रशिक्षण के लिए कार्य के कोड में प्रस्तुत किया गया है।
  // वर्णमाला का आकार माना शब्दों में कास्ट इंट अल्फा = 26; // ड्रिल के शीर्ष के लिए संरचना संरचना नोड { // आसन्न तालिका के रूप में किनारों का वेक्टर, वह है: // अगला [0] - चरित्र संख्या 0 पर कूदने पर बच्चा ('a') // अगला [1] - चरित्र संख्या 1 ('b') पर कूदने पर बच्चा // वगैरह। वेक्टरअगला; // अतिरिक्त विकल्प // इस मामले में, वर्टेक्स एच की ऊंचाई और टर्मिनलिटी का झंडा इंट एच; बूल शब्द ;; नोड (इंट एच) { next.resize(alph, -1); // शुरू में किनारों के बिना यह->एच = एच; // ऊंचाई निर्दिष्ट के बराबर है पद = असत्य; // शीर्ष डिफ़ॉल्ट रूप से टर्मिनल नहीं है } }; // कोने की सूची, प्रारंभ में शून्य ऊंचाई पर जड़ वेक्टर <नोड> ट्राई (1, नोड (0)); // बोरॉन में एक स्ट्रिंग जोड़ने के लिए फ़ंक्शन शून्य जोड़ें (स्थिरांक स्ट्रिंग और एस) { इंट वी = 0; // वर्तमान शीर्ष की संख्या, जड़ से शुरू forn (i, (int) s.size ()) { int c = s[i] - 'a'; // स्ट्रिंग में वर्तमान वर्ण की संख्या प्राप्त करें // यदि वांछित संक्रमण अभी तक मौजूद नहीं है, तो हम एक नया बना देंगे अगर (कोशिश [वी]। अगला [सी] == -1) { ट्राई [वी] .नेक्स्ट [सी] = (इंट) ट्राई.साइज (); // नया वर्टेक्स नंबर है   // वर्तमान ड्रिल आकार (0-नंबरिंग के साथ) trie.push_back (नोड (trie [v] .h + 1)); // ऊंचाई 1 और के साथ एक नया शीर्ष बनाएँ } वी = ट्राई [वी] अगला [सी]; // वांछित किनारे के साथ आगे बढ़ें } // जब हम शीर्ष पर पहुंचे,   // जो पूरी स्ट्रिंग से मेल खाता है,   // फिर इसे टर्मिनल के रूप में चिह्नित करें ट्राई [वी] .टर्म = सच; }
यदि आपको बोरॉन से पंक्तियों को हटाने का समर्थन करने की आवश्यकता है, तो यह संभवतः बेईमानी होगी। यानी, बस टर्मिनल फ्लैग को हटा दें (या, शायद, फ्लैग के बजाय, आपको एक वेरिएबल नंबर स्टोर करने की आवश्यकता होगी), और बोरॉन ट्री को अपरिवर्तित छोड़ दें।

इस प्रकार, सम्मिलन/खोज/अनुचित विलोपन क्वेरी स्ट्रिंग की लंबाई से रैखिक समय में कार्य करता है।

सबसे खराब स्थिति में, बोरॉन स्वयं O(n|Σ|) मेमोरी पर कब्जा कर लेगा, जहां n सभी स्ट्रिंग्स की कुल लंबाई है, और Σ > - प्रयुक्त स्ट्रिंग्स की वर्णमाला।