मैं एक साक्षात्कार के लिए दिखाई दिया जहां मुझे आंशिक कुंजी हैशिंग i.e के लिए एक एल्गोरिदम लिखने के लिए कहा गया था; यदि हैश में एबीसीबीसी डाली गई है तो किसी भी उप स्ट्रिंग को खोजना मूल्य को वापस लौटा देना चाहिए। मेरा उत्तर किसी दिए गए कुंजी के सभी संभावित सबस्ट्रिंग का संग्रह बनाना था और प्रत्येक ऑब्जेक्टिंग के बीच मैपिंग को एक या अधिक पैरेंट स्ट्रिंग में बनाए रखना था। फिर सभी सबस्ट्रिंग्स के संग्रह का एक बीएसटी बनाए रखें। प्रत्येक नोड वास्तविक मानों के संग्रह को इंगित करेगा जो कि सबस्ट्रिंग से मेल खा सकता है। उदाहरण के लिए । ए, एबी, एबीसी, एबीसीबी, एबीसीबीसी, बी, बीसी, बीसीबी, बीसीबीसी, सी, सीबी, सीबीसी इस स्ट्रिंग के लिए संभावित सबस्ट्रिंग हैं। बीएबी की तरह अन्य तार भी हो सकते हैं, जिनमें से एबी और बी का सबस्ट्रिंग होता है। तो एबी दिया गया, यह दो तारों बीएबी और एबीसीबीसी को मैप करेगा।आंशिक कुंजी हैशिंग को लागू करने का सबसे अच्छा तरीका है
क्या कोई और अधिक प्रभावी तरीका है? धन्यवाद
आप एक हैशटेबल में सबस्ट्रिंग नोड्स को स्टोर कर सकते हैं (सबस्ट्रिंग मान पर हैशिंग, जाहिर है)। यह आपकी खोज को ओ (लॉग एन) से ओ (1) में काट देगा। अंतरिक्ष जटिलता तुलनात्मक या थोड़ा बदतर होगी (तालिका में खाली स्लॉट के कारण)। – jpm
ऐसा लगता है कि प्रत्येक सबस्ट्रिंग के लिए हैश बनाने में असुरक्षित हो सकता है ... शायद यहां एक अलग चाल चल रही है? उपसर्ग पेड़ के साथ प्रयोग करने योग्य कुछ भी? –
प्रत्यय पेड़ (http://en.wikipedia.org/wiki/Suffix_tree) शायद, हालांकि यह वास्तव में "हैशिंग" नहीं है। मैं वास्तव में समझ नहीं पा रहा हूं कि समग्र संग्रह कैसे काम करता है: मान लीजिए कि मैं एबीसीबीसी को 4 के मान के साथ सम्मिलित करता हूं। फिर एबीसी के लिए खोज 4, काफी उचित है। क्या होगा यदि मैं 5 के मूल्य के साथ सीडीएबीसी भी डालूं। अब एबीसी रिटर्न की खोज क्या है? आप यह नहीं कह सकते कि "संग्रहीत मूल्य वापस करना चाहिए" और यह भी कहें, "यह दो तारों पर मैप करेगा", क्योंकि यह दोनों नहीं कर सकता है। –