आप निम्नलिखित के आधार पर चक्रीय तार के लिए एक canonicalizing समारोह के साथ आ सकता है:
- शून्य का सबसे बड़ा भाग खोजें।
- स्ट्रिंग घुमाएं ताकि ज़ीरो का वह भाग सामने हो।
- बराबर आकार के शून्य के प्रत्येक भाग के लिए, देखें कि सामने के घूर्णन को लेक्सिकोग्राफिक रूप से कम स्ट्रिंग का उत्पादन होता है और यदि ऐसा है तो इसका उपयोग करें।
यह कोषगत कम से कम मूल्य के लिए तुल्यता वर्ग में सब कुछ (1011, 1101, 1110, 0111) canonicalize होगा: 0111.
0101010101 एक कांटेदार उदाहरण जिसके लिए इस algo अच्छा प्रदर्शन नहीं करेगा है, लेकिन यदि आपकी बिट्स मोटे तौर पर बेतरतीब ढंग से वितरित की जाती हैं, तो इसे लंबे तारों के लिए अभ्यास में अच्छी तरह से काम करना चाहिए।
फिर आप कैनोनिकल रूप के आधार पर हैश का उपयोग कर सकते हैं या एक त्रिभुज का उपयोग कर सकते हैं जिसमें केवल खाली स्ट्रिंग और तार शामिल होंगे जो 0 से शुरू होते हैं और एक तिहाई रन आपके प्रश्न का उत्तर देगा।
संपादित करें:
अगर मैं लंबाई के एक स्ट्रिंग है | | s कम से कम शब्दावली मूल्य खोजने में काफी समय लग सकता है .. वास्तव में यह कितना समय लगेगा?
यही कारण है कि मैंने कहाएक मूल्य है जिसके लिए यह बुरी तरह से प्रदर्शन करता है। आइए मान लें कि स्ट्रिंग लंबाई एन है और 1 का लंबा सबसे लंबा भाग आर है। यदि बिट्स को यादृच्छिक रूप से वितरित किया जाता है, तो सबसे लंबे समय तक चलने की लंबाई ओ (लॉग एन) "Distribution of longest run" के अनुसार होती है।
सबसे लंबा रन खोजने का समय ओ (एन) है। आप एक बफर प्रतिलिपि के बजाय ऑफसेट का उपयोग करके स्थानांतरण को कार्यान्वित कर सकते हैं, जो ओ (1) होना चाहिए। रनों की संख्या सबसे खराब स्थिति ओ (एन/एम) है।
फिर, समय चरण 3 करने के लिए किया जाना चाहिए
- अन्य लंबी रन खोजें: एक हे (एन) हे (लॉग एन) भंडारण औसत मामले से गुजरती हैं, हे (एन) सबसे ज्यादा मामले
- प्रत्येक रन के लिए: ओ (लॉग एन) औसत मामला, ओ (एन) सबसे खराब मामला
- शिफ्ट और लेक्सिकोग्राफिक रूप से तुलना करें: ओ (लॉग एन) औसत केस, क्योंकि यादृच्छिक रूप से चुने हुए स्ट्रिंग की अधिकांश तुलना जल्दी विफल हो जाती है, ओ (एन) सबसे खराब मामला ।
यह ओ (एन²) का सबसे खराब मामला है, लेकिन ओ (एन + लॉग² एन) ≅ ओ (एन) का औसत मामला है।
स्रोत
2012-01-20 20:49:19
यदि यह उन दो से अधिक पात्रों में से एक वर्णमाला के लिए है, मैं एक हैश समारोह है कि एक ही परिणाम चरित्र मानों का क्रम की परवाह किए बिना उत्पन्न बनाने कहेंगे, ताकि आप जल्दी से सबसे गैर मैचों समाप्त कर सकते हैं। –
@ सीवेनहुइस: नहीं, मैं केवल बाइनरी तारों के साथ काम कर रहा हूं। – user550413
क्या आप सभी सम्मिलन ऊपर-सामने करते हैं? या आप सम्मिलन और लुकअप intermix करते हैं? – templatetypedef