Lexicographically minimal string rotation
कंप्यूटर विज्ञान में, लेक्सिकोग्राफिक रूप से न्यूनतम स्ट्रिंग रोटेशन या लेक्सिकोग्राफिक रूप से सबसे कम गोलाकार सबस्ट्रिंग ऐसे सभी रोटेशनों के सबसे कम लेक्सिकोग्राफिक क्रम वाले स्ट्रिंग के रोटेशन को खोजने की समस्या है। उदाहरण के लिए, "bbaaccaadd" का शब्दकोशात्मक रूप से न्यूनतम आवर्तन "aaccaaddbb" होगा। एक स्ट्रिंग के लिए कई लेक्सिकोग्राफिक रूप से न्यूनतम घूर्णन होना संभव है, लेकिन अधिकांश अनुप्रयोगों के लिए यह मायने नहीं रखता है क्योंकि घूर्णन समतुल्य होना चाहिए। शब्दकोषीय रूप से न्यूनतम घूर्णन का पता लगाना तारों को सामान्य बनाने के तरीके के रूप में उपयोगी है। यदि तार ग्राफ जैसी संभावित समरूप संरचनाओं का प्रतिनिधित्व करते हैं, तो इस तरह से सामान्यीकरण सरल समानता जांच के लिए अनुमति देता है। वृत्ताकार तारों के साथ काम करते समय एक सामान्य कार्यान्वयन चाल स्ट्रिंग सूचकांकों पर मॉड्यूलर अंकगणितीय प्रदर्शन करने के बजाय स्ट्रिंग को स्वयं से जोड़ना है। एल्गोरिदम द नाइव एल्गोरिदम एक स्ट्रिंग के लेक्सिकोग्राफिक रूप से न्यूनतम घूर्णन का पता लगाने के लिए सरल एल्गोरिदम सबसे लेक्सिकोग्राफिक रूप से न्यूनतम घूर्णन का सामना करते हुए क्रमिक घूर्णन के माध्यम से पुनरावृत्ति करना है। यदि स्ट्रिंग की लंबाई है, तो यह एल्गोरिथ्म सबसे खराब स्थिति में समय पर चलता है। बूथ का एल्गोरिदम बूथ (1980) द्वारा एक कुशल एल्गोरिदम प्रस्तावित किया गया था। एल्गोरिथ्म क्नुथ-मोरिस-प्राट स्ट्रिंग खोज एल्गोरिथ्म से एक संशोधित प्रीप्रोसेसिंग फ़ंक्शन का उपयोग करता है। स्ट्रिंग के लिए विफलता फ़ंक्शन की गणना सामान्य के रूप में की जाती है, लेकिन गणना के दौरान स्ट्रिंग को घुमाया जाता है इसलिए कुछ सूचकांकों को एक से अधिक बार गणना की जानी चाहिए क्योंकि वे चारों ओर लपेटते हैं। एक बार जब विफलता फलन के सभी सूचकांकों की गणना स्ट्रिंग को फिर से घुमाने के बिना सफलतापूर्वक की जाती है, तो न्यूनतम लेक्सिकोग्राफिक रोटेशन पाया जाता है और इसका प्रारंभिक सूचकांक वापस आ जाता है। एल्गोरिदम की शुद्धता को समझना कुछ मुश्किल है, लेकिन इसे लागू करना आसान है। डेफ लीस्ट रोटेशन (s: str)-> int: "बूथ का लेक्सिकोग्राफिक रूप से न्यूनतम स्ट्रिंग रोटेशन एल्गोरिथ्म"। एन = लेन (एस) एफ = [-1] * (2 * एन) के = 0 जे के लिए सीमा (1,2 * एन): आई = एफ [जे-के-1] जबकि आई! =-1 और एस [जे% एन]! = एस [(के + आई + 1)% एन]: अगर एस [जे% एन] <एस [(के + आई + 1)% एन]: के = जे-आई-1 आई = एफ [आई] अगर आई = = और एस [जे% एन] = एस [(के + आई + 1)% एन]: अगर एस [जे% एन] <एस [(के + आई + 1)% एन]: के = बूथ का एल्गोरिथ्म समय पर चलता है, जहाँ स्ट्रिंग की लंबाई है। एल्गोरिथ्म सबसे खराब स्थिति में अधिकांश तुलनाओं में प्रदर्शन करता है, और विफलता फ़ंक्शन तालिका को पकड़ने के लिए लंबाई की सहायक स्मृति की आवश्यकता होती है। शिलोच के फास्ट कैनोनाइजेशन एल्गोरिदम शिलोच (1981) ने प्रदर्शन के मामले में बूथ के परिणाम में सुधार के लिए एक एल्गोरिदम का प्रस्ताव रखा। यह देखा गया कि यदि लंबाई की एक स्ट्रिंग के समतुल्य लेक्सिकोग्राफिक रूप से न्यूनतम घूर्णन हैं, तो स्ट्रिंग में लंबाई के समान सबस्ट्रिंग होने चाहिए। एल्गोरिथ्म को सबसे खराब स्थिति में केवल तुलना और निरंतर स्थान की आवश्यकता होती है। एल्गोरिथ्म को दो चरणों में विभाजित किया गया है। पहला चरण एक त्वरित छलनी है जो उन सूचकांकों को निर्धारित करता है जो स्पष्ट रूप से शब्दकोषीय रूप से न्यूनतम घूर्णन के लिए प्रारंभिक स्थान नहीं हैं। दूसरा चरण तब शेष सूचकांकों से लेक्सिकोग्राफिक रूप से न्यूनतम घूर्णन प्रारंभ सूचकांक पाता है। डुवल के लिंडन फैक्टराइजेशन एल्गोरिदम डुवल (1983) ने एक कुशल एल्गोरिदम का प्रस्ताव रखा जिसमें स्ट्रिंग के घटक लिंडन शब्दों में फैक्टराइजेशन शामिल है, जो एक निरंतर स्मृति आवश्यकता के साथ रैखिक समय में चलता है। वेरिएंट्स शिलोच (1979) ने एक सामान्यीकरण आवश्यकता के बिना समानता के लिए दो गोलाकार तारों की कुशलता से तुलना करने के लिए एक एल्गोरिथ्म का प्रस्ताव रखा। एक अतिरिक्त अनुप्रयोग जो एल्गोरिथ्म से उत्पन्न होता है, वह है दोहराव के बिना कुछ रासायनिक संरचनाओं का तेजी से उत्पादन। लिंडन शब्द क्नुथ-मोरिस-प्राट एल्गोरिथ्म भी देखें संदर्भ स्ट्रिंग्स पर समस्याएं लेक्सिकोग्राफी उदाहरण कोड के साथ लेख