आप Ukkonen एल्गोरिथ्म का उपयोग कर सकते रैखिक समय में एक प्रत्यय पेड़ के निर्माण के लिए:
https://en.wikipedia.org/wiki/Ukkonen%27s_algorithm
रों की सबस्ट्रिंग की संख्या तो trie, तो आप बस गणना कर सकते हैं, जिसमें तार के उपसर्गों की संख्या है रैखिक समय में। यह सभी नोड्स में वर्णों की कुल संख्या है। पेड़ में
/\
b a
| b
b b
5 अक्षर, तो 5 सबस्ट्रिंग:
उदाहरण के लिए, अपने उदाहरण की तरह एक प्रत्यय पेड़ पैदा करता है। प्रत्येक अद्वितीय स्ट्रिंग एक अलग अक्षर के बाद समाप्त होने वाली जड़ से एक पथ है: abb, ab, a, bb, b। तो तारों की संख्या पेड़ में अक्षरों की संख्या है।
अधिक स्पष्ट:
- हर-स्ट्रिंग स्ट्रिंग के कुछ प्रत्यय उपसर्ग है;
- सभी प्रत्यय trie में हैं;
- तो त्रिभुज (त्रिभुज की परिभाषा के अनुसार) के माध्यम से सबस्ट्रिंग्स और पथों के बीच 1-1 पत्राचार होता है;
- प्रत्येक विशिष्ट गैर खाली पथ अपने पिछले पत्र के बाद एक अलग स्थिति में समाप्त होता है;: और
- वहाँ क्योंकि, पेड़ और गैर खाली रास्तों में अक्षरों के बीच 1-1 से पत्राचार है और
- स्थिति प्रत्येक अक्षर के निम्नलिखित के लिए पथ अद्वितीय लोग हैं, जो सोच रहे हैं कि यह कैसे एक पेड़ है कि हे में हे (एन^2) वर्ण हैं का निर्माण संभव हो सकता है के लिए
नोट है (एन) समय:
प्रत्यय वृक्ष के प्रतिनिधित्व के लिए एक चाल है। पेड़ के नोड्स में वास्तविक तारों को संग्रहीत करने के बजाय, आप केवल ओरिएंटल स्ट्रिंग में पॉइंटर्स स्टोर करते हैं, इसलिए "abb" वाले नोड में "abb" नहीं है, इसमें प्रति (0,3) - 2 पूर्णांक हैं नोड, इस पर ध्यान दिए बिना कि प्रत्येक नोड में स्ट्रिंग कितनी देर तक है, और प्रत्यय के पेड़ में ओ (एन) नोड्स हैं।
स्रोत
2016-01-19 18:17:57
'बीए' एबीबी का एक सबस्ट्रिंग नहीं है। – gnasher729
@ gnasher729 आप सही हैं, किसी ने इसे पहले ही संपादित कर लिया है। – donrondon
मुझे लगता है कि यह प्रश्न यहां होना चाहिए: https://cs.stackexchange.com/ – ChaosPredictor