python - एक विभाजन से अधिकतम सबस्ट्रिंग की अधिकतम संख्या




string algorithm (5)

(इस चर्चा से मुझे अवगत कराने के लिए गिल्ड बार्कन (דלעב ברק for) को बहुत-बहुत धन्यवाद।)

मुझे इस समस्या के बारे में अपने विचारों को विशुद्ध सैद्धांतिक दृष्टिकोण से साझा करने दें (ध्यान दें कि मैं "सबवेर्ड" के बजाय "कारक" का उपयोग करता हूं)।

मुझे लगता है कि इस समस्या (या समस्याओं) की एक पर्याप्त औपचारिक परिभाषा निम्नलिखित है:

एक शब्द w को देखते हुए, शब्द u_1, u_2, ..., u_k को ऐसे खोजें

  • u_i! = u_j हर i, j के साथ 1 <= i <j <= k और
  • u_1 u_2 ... u_k = w

अधिकतमकरण संस्करण (हम कई u_i चाहते हैं): अधिकतम कश्मीर

न्यूनतमकरण संस्करण (हम छोटा u_i चाहते हैं): अधिकतम घटाएँ {| u_i | : 1 <= i <= k}

ये समस्याएं अतिरिक्त रूप से एक बाध्य बी देने से निर्णय की समस्या बन जाती हैं, जिसके अनुसार, हम "कई-कारकों" के बारे में बात कर रहे हैं -variant या "छोटे कारक" -variant, k पर कम बाध्य है (हम कम से कम B चाहते हैं कारकों), या अधिकतम पर एक ऊपरी बाध्य {| u_i | : 1 <= i <= k} (हम सबसे बी में लंबाई के कारक चाहते हैं), क्रमशः। एनपी-कठोरता के बारे में बात करने के लिए, हमें निर्णय समस्याओं के बारे में बात करने की आवश्यकता है।

आइए "छोटे कारकों" के लिए एसएफ शब्द का उपयोग करें - "वेरिएंट" और "एमएफ" के लिए "कई कारक"। विशेष रूप से, और यह वास्तव में एक महत्वपूर्ण बिंदु है, समस्याओं को इस तरह से परिभाषित किया जाता है कि हमें कुछ वर्णमाला पर एक शब्द मिलता है जो किसी भी तरह से प्रतिबंधित नहीं है। समस्या संस्करण था कि हम एक प्राथमिकता जानते हैं कि हमें केवल इनपुट शब्द मिलते हैं, कहते हैं, वर्णमाला {a, b, c, d} एक अलग समस्या है! एनपी-कठोरता स्वचालित रूप से "अप्रतिबंधित" से "निश्चित वर्णमाला" संस्करण (उत्तरार्द्ध सरल हो सकता है) पर नहीं ले जाती है।

एसएफ और एमएफ दोनों एनपी-पूर्ण समस्याएं हैं। यह क्रमशः [1, 1 बी] और [2] में दिखाया गया है (जैसा कि गिलाद ने पहले ही बताया है)। अगर मैं इस चर्चा की शुरुआत में (शायद) भी अनौपचारिक समस्या की परिभाषा को सही ढंग से समझता हूं, तो इस चर्चा की समस्या बिल्कुल समस्या एमएफ है। यह शुरू में उल्लेख नहीं किया गया है कि शब्द कुछ निश्चित वर्णमाला से आने के लिए प्रतिबंधित हैं, बाद में यह कहा जाता है कि हम मान सकते हैं कि केवल निचले-मामले वाले अक्षरों का उपयोग किया जाता है। यदि इसका अर्थ है कि हम केवल निश्चित वर्णमाला {a, b, c, ..., z} पर शब्दों पर विचार करते हैं, तो यह वास्तव में NP-कठोरता के संदर्भ में बहुत कुछ बदल देगा।

एक नज़दीकी नज़र से एसएफ और एमएफ की जटिलता में कुछ अंतर का पता चलता है:

  1. कागज [1, 1 बी] से पता चलता है कि यदि हम एक द्विआधारी एक को वर्णमाला को ठीक करते हैं तो एसएफ एनपी-पूर्ण रहता है (अधिक सटीक रूप से: अक्षरों और बी पर एक शब्द डब्ल्यू प्राप्त करना और एक बाध्य बी, क्या हम इसे लंबाई के अलग-अलग कारकों में बता सकते हैं। अधिकांश बी;)।
  2. कागज [1, 1 बी] से पता चलता है कि यदि हम बाध्य बी = 2 को ठीक करते हैं तो एसएफ एनपी-पूर्ण रहता है (अधिक सटीक रूप से: एक शब्द डब्ल्यू प्राप्त करना, क्या हम इसे अधिकतम 2 में लंबाई के विभिन्न कारकों में बदल सकते हैं?)।
  3. कागज [3] से पता चलता है कि यदि वर्णमाला और बाउंड बी दोनों तय हो गए हैं, तो एसएफ को बहुपद-समय में हल किया जा सकता है।
  4. कागज [2] से पता चलता है कि एमएफ एनपी-पूर्ण है, लेकिन केवल अगर वर्णमाला प्रतिबंधित नहीं है या एक प्राथमिकता तय नहीं है ! विशेष रूप से, यह सवाल का जवाब नहीं देता है यदि समस्या एनपी-पूर्ण है यदि हम केवल कुछ निश्चित वर्णमाला पर इनपुट शब्दों पर विचार करते हैं (जैसा कि व्यावहारिक सेटिंग्स में सामान्य रूप से होता है)।
  5. पेपर [3] से पता चलता है कि म्यूचुअल फंड बहुपत्नी समय में हल किया जा सकता है अगर इनपुट सीमा बी फिर से कुछ निरंतर द्वारा बंधी हुई है, अर्थात, समस्या इनपुट एक शब्द है और {1, 2, ..., K} से एक ब B है। , जहां K कुछ स्थिर है।

इन परिणामों पर कुछ टिप्पणियाँ: Wrt (1) और (2), यह सहज रूप से स्पष्ट है कि यदि वर्णमाला द्विआधारी है, तो, समस्या को SF मुश्किल बनाने के लिए, बाध्य B को भी ठीक नहीं किया जा सकता है। इसके विपरीत, B = 2 को ठीक करने का अर्थ है कि कठिन उदाहरणों को उत्पन्न करने के लिए वर्णमाला का आकार बड़ा होना चाहिए। परिणाम के रूप में, (3) बल्कि तुच्छ है (वास्तव में, [3] थोड़ा और कहते हैं: हम इसे चलाने के समय में हल कर सकते हैं न केवल बहुपद, बल्कि w | ^ 2 बार एक कारक है जो केवल वर्णमाला के आकार पर निर्भर करता है और बाध्य बी)। (5) मुश्किल भी नहीं है: यदि हमारा शब्द बी की तुलना में लंबा है, तो हम अलग-अलग लंबाई के कारकों में बस ढलान से वांछित कारक प्राप्त कर सकते हैं। यदि नहीं, तो हम सभी संभावनाओं को बल दे सकते हैं, जो केवल बी में घातीय है, जो इस मामले में एक स्थिर माना जाता है।

तो हमारे पास जो चित्र है वह निम्न है: एसएफ अधिक कठिन लगता है, क्योंकि हमारे पास निश्चित अल्फाबेट्स के लिए या एक निश्चित बाध्य बी के लिए भी कठोरता है। समस्या एमएफ, दूसरी तरफ, पॉली-टाइम सॉल्व हो जाती है यदि बाउंड तय हो गया है (में इस संबंध में यह SF की तुलना में आसान है), जबकि संबंधित प्रश्न में वर्णमाला का आकार खुला है। इसलिए एमएफ एसएफ की तुलना में थोड़ा कम जटिल है, भले ही यह पता चला हो कि निश्चित वर्णमाला के लिए एमएफ भी एनपी-पूर्ण है। हालांकि, अगर यह दिखाया जा सकता है कि पॉली-टाइम में निश्चित वर्णमाला के लिए एमएफ को हल किया जा सकता है, तो एमएफ को एसएफ की तुलना में बहुत आसान दिखाया जाता है ... क्योंकि एक मामला जिसके लिए यह कठिन है वह कुछ हद तक कृत्रिम (अनबाउंड वर्णमाला है!)। ।

मैंने एमएफ के मामले को बाध्य वर्णमाला के साथ हल करने की कोशिश में कुछ प्रयास किया, लेकिन मैं इसे निपटाने में सक्षम नहीं था और इसके बाद से काम करना बंद कर दिया। मुझे विश्वास नहीं है कि अन्य शोधकर्ताओं ने इसे हल करने की बहुत कोशिश की है (इसलिए यह इन बहुत कठिन खुली समस्याओं में से एक नहीं है, कई लोग पहले ही कोशिश कर चुके हैं और असफल रहे; मैं इसे किसी भी तरह से उचित मानता हूं)। मेरा अनुमान है कि यह फिक्स्ड अल्फाबेट्स के लिए एनपी-हार्ड भी है, लेकिन शायद कमी इतनी जटिल है कि आपको "एमएफ का आकार 35 या उससे अधिक के अल्फा के लिए कठिन है" या ऐसा कुछ मिलेगा, जो सुपर अच्छा भी नहीं होगा ।

आगे के साहित्य के बारे में, मैं कागज [4] को जानता हूं, जो शब्द को अलग-अलग कारकों में विभाजित करने की समस्या पर विचार करता है u_1, u_2, ..., u_k जो सभी पैलिंड्रोम हैं, जो एनपी-पूर्ण भी है।

गिल्ड द्वारा इंगित किए गए कागज [5] पर मेरी त्वरित नज़र थी। यह एक अलग सेटिंग पर विचार करता है, हालांकि। इस पत्र में, लेखक इस बात की दिलचस्पी रखते हैं कि किसी दिए गए शब्द में कितने विशिष्ट अनुगामी या उपशब्द शामिल किए जा सकते हैं, लेकिन ये ओवरलैप हो सकते हैं। उदाहरण के लिए, आआबाब में 20 अलग-अलग उप-शब्द होते हैं a, b, aa, ab, ba, bb, aaa, aab, aba, baa, aab, aaba, abab, baab, aaaba, aabaa, abaab, aabaab, aaaba, (शायद मैं) दुस्साहस, लेकिन आप विचार प्राप्त करते हैं)। उनमें से कुछ की एक ही घटना होती है, जैसे बा, उनमें से कुछ कई, जैसे कि आ। किसी भी मामले में, सवाल यह नहीं है कि हम कई अलग-अलग कारकों को प्राप्त करने के लिए किसी तरह शब्द को कैसे विभाजित कर सकते हैं, क्योंकि इसका मतलब है कि प्रत्येक व्यक्ति का प्रतीक बिल्कुल एक कारक में योगदान देता है।

इस तरह की समस्याओं के व्यावहारिक समाधान के बारे में (ध्यान रखें कि मैं एक सिद्धांतवादी हूं, इसलिए इसे नमक के दाने के साथ लें):

  • मेरी जानकारी के लिए, कोई सैद्धांतिक निचली सीमा (जैसे कि एनपी-कठोरता) नहीं है जो कि बहुपदीय समय में एमएफ को हल करने के लिए इसे नियंत्रित करेगा यदि हम एक निश्चित वर्णमाला पर केवल इनपुट शब्दों पर विचार करते हैं। एक चेतावनी है, हालांकि: यदि आपको पॉली-टाइम एल्गोरिथ्म मिलता है, तो यह निश्चित वर्णमाला (या किसी फ़ंक्शन में घातीय) से प्रतीकों की संख्या में तेजी से चलना चाहिए! अन्यथा यह अनबाउंड अल्फाबेट्स के मामले के लिए एक बहुपद समय एल्गोरिथ्म भी होगा। इसलिए, एक सैद्धांतिक होने के नाते, मैं एल्गोरिदम कार्यों की तलाश करूंगा जो कि समय के घातांक में गणना की जा सकती हैं यदि केवल प्रतीकों की संख्या और जो किसी तरह एमएफ के लिए एल्गोरिदम को तैयार करने में मदद करते हैं। दूसरी ओर, यह संभावना है कि ऐसा एल्गोरिथ्म मौजूद नहीं है और फिक्स्ड-अल्फाबेट मामले में एमएफ भी एनपी-हार्ड है।

  • यदि आप व्यावहारिक समाधानों में रुचि रखते हैं, तो समाधान का अनुमान लगाना मददगार हो सकता है। इसलिए फैक्टरिसेशन जो केवल आधे के रूप में बड़े होने की गारंटी है, सबसे खराब स्थिति में इष्टतम भी खराब नहीं होगा।

  • अनुमान है कि एक स्पष्ट अनुमान अनुपात नहीं देते हैं, लेकिन एक व्यावहारिक सेटिंग में अच्छी तरह से काम भी दिलचस्प होगा, मुझे लगता है।

  • समस्या उदाहरणों को SAT या ILP- इंस्टेंसेस में बदलना बहुत कठिन नहीं होना चाहिए और तब आप एक SAT या ILP-सॉल्वर भी इष्टतम समाधान प्राप्त करने के लिए चला सकते हैं।

  • मेरी व्यक्तिगत राय है कि भले ही यह ज्ञात नहीं है कि एमएफ का निश्चित-वर्णमाला मामला एनपी-हार्ड है, पर्याप्त सैद्धांतिक अंतर्दृष्टि है जो सुझाव देती है कि समस्या काफी कठिन है ताकि हेयुरिस्टिक समाधानों की तलाश करना उचित हो। व्यावहारिक सेटिंग में अच्छी तरह से काम करें।

ग्रंथ सूची:

[१] ऐनी कोंडन, जान मनुच, क्रिस थचुक: स्ट्रिंग विभाजन की जटिलता। जे। असतत एल्गोरिदम 32: 24-43 (2015)

[१ बी] ऐनी कोंडॉन, जान मनुच, क्रिस थचुक: एक टक्कर की जटिलता-अवेयर स्ट्रिंग विभाजन की समस्या और जीन सिंथेसिस के लिए ओलिगो डिजाइन से इसका संबंध। COCOON 2008: 265-275

[२] हेनिंग फर्नाउ, फ्लोरिन मैना, रॉबर्ट मर्कस, मार्कस एल। श्मिड: वेरिएबल्स के साथ पैटर्न मैचिंग: फास्ट एलगोरिदम और न्यू हार्डनेस परिणाम। STACS 2015: 302-315

[३] मार्कस एल। श्मिट: समानता-मुक्त और दोहराए जाने वाले स्ट्रिंग कारक। या। कंप्यूटर। विज्ञान। 618: 42-51 (2016)

[४] हिदेओ बन्नई, ट्रैविस गगी, शुन्सुके इनेनगा, जुहा किर्ककेंन, डॉमिनिक केम्पा, मार्सिन पिआटकोस्की, शिहो सुगिमोटो: डायवर्स पेलियोक्रोमिक फैक्टराइजेशन एनपी-कम्प्लीट है। इंट। जे। पाया। कंप्यूटर। विज्ञान। 29 (2): 143-164 (2018)

[५] अब्राहम फ्लैक्समैन, अराम वेट्रॉथ हैरो, ग्रेगरी बी। सोरकिन: स्ट्रिंग्स विद मैक्सिमली कई डिस्टि्रक्ट सब्जेक्ट्स एंड सबस्ट्रिंग्स। Electr। जे। कंघी। 11 (1) (2004)

शीर्षक को थोड़ा और संशोधित करके इसे और अधिक समझने योग्य बनाया जा सकता है।

यहाँ विस्तृत संस्करण है। माना कि हमारे पास एक स्ट्रिंग s , हम इसे कुछ सबस्ट्रिंग में विभाजित करना चाहते हैं। प्रत्येक स्थानापन्न एक दूसरे से भिन्न होता है। अद्वितीय पदार्थों की अधिकतम संख्या क्या है जिसे हम एक कट से प्राप्त कर सकते हैं। दूसरे शब्दों में, आप उन सबस्ट्रेट्स को समाप्‍त करके s को पुनर्प्राप्त कर सकते हैं।

यहाँ कुछ उदाहरण हैं:

Example 1
s = 'aababaa'
output = 4
Explain: we can split it into aa|b|aba|a or aab|a|b|aa, 
         and 4 is the max number of substrings we can get from one split.

Example 2
s = 'aba'
output = 2
Explain: a|ba

Example 3
s = 'aaaaaaa'
output = 3
Explain: a|aa|aaaa

नोट : केवल लोअरकेस वर्ण शामिल हैं। यह निश्चित नहीं है कि यह कितना लंबा है जो मुझे इष्टतम समय जटिलता का अनुमान नहीं लगा सकता है। :(

क्या यह एनपी-कठिन समस्या है? यदि नहीं, तो इसे कुशलता से कैसे हल करें?

मैंने अपने एक मित्र से यह समस्या सुनी। और मैं इसे बाहर नहीं निकाल सका। मैं इस समस्या को हल करने के लिए एक Trie + लालची का उपयोग करने की कोशिश कर रहा हूं। लेकिन यह पहले उदाहरण पर विफल रहता है।

यहाँ है कि मैं के साथ आया trie समाधान है:

def triesolution(s):
    trie = {}
    p = trie
    output = 0
    for char in s:
        if char not in p:
            output += 1
            p[char] = {}
            p = trie
        else:
            p = p[char]
    return output

उदाहरण 1 के लिए, उपरोक्त कोड 3 वापस आ जाएगा, क्योंकि यह इसे a|ab|abaa में विभाजित करने का प्रयास कर रहा है।

जोड़ें: सभी के विचार का धन्यवाद, ऐसा लगता है कि यह समस्या एक एनपी समस्या के बहुत करीब है। अभी, मैं इस दिशा से सोचने की कोशिश कर रहा हूं। मान लीजिए हमारे पास एक फ़ंक्शन है Guess(n) । यह फ़ंक्शन True लौटेगा यदि हम एक स्प्लिट या False अन्यथा अनूठे सबस्ट्रिंग पा सकते हैं। यहाँ एक अवलोकन यह है कि यदि Guess(n) == True , तो Guess(i) == True सभी के लिए Guess(i) == True i <= n । चूंकि हम दो आसन्न पदार्थों को एक साथ मिला सकते हैं। इस अवलोकन से एक द्विआधारी समाधान हो सकता है। हालाँकि, यह अभी भी आवश्यकता है कि हम बहुत ही कुशलता से Guess फ़ंक्शन की गणना कर सकते हैं। अफसोस की बात है, मैं अभी भी Guess(n) गणना करने के लिए एक बहुपद तरीके का पता नहीं लगा सका।


आप वर्तमान पथ में अद्वितीय तारों का ट्रैक रखने के लिए एक दूसरे पैरामीटर के रूप में सेट के साथ एक पुनरावर्ती फ़ंक्शन का उपयोग कर सकते हैं। प्रत्येक पुनरावृत्ति के लिए, सभी सूचकांकों प्लस 1 के माध्यम से पुनरावृत्ति करें, जिस पर एक संभावित उम्मीदवार स्ट्रिंग के लिए स्ट्रिंग को विभाजित करने के लिए, और यदि उम्मीदवार स्ट्रिंग अभी तक सेट में नहीं है, तो शेष स्ट्रिंग के साथ एक पुनरावर्ती कॉल करें और उम्मीदवार को सेट में जोड़ा जाए। शेष स्ट्रिंग से अधिकतम संख्या में अनूठे पदार्थ प्राप्त करने के लिए, इसमें 1 जोड़ें और पुनरावृत्तियों से अधिकतम अधिकतम रिटर्न प्राप्त करें। रिटर्न 0 अगर या तो दिया गया स्ट्रिंग खाली है या सभी उम्मीदवार के तार पहले से ही सेट में हैं:

def max_unique_substrings(s, seen=()):
    maximum = 0
    for i in range(1, len(s) + 1):
        candidate = s[:i]
        if candidate not in seen:
            maximum = max(maximum, 1 + max_unique_substrings(s[i:], {candidate, *seen}))
    return maximum

डेमो: https://repl.it/@blhsing/PriceyScalySphere

पायथन 3.8 में, उपरोक्त तर्क को एक जनरेटर अभिव्यक्ति के साथ max फ़ंक्शन के लिए कॉल के साथ भी लिखा जा सकता है जो उम्मीदवारों को एक असाइनमेंट अभिव्यक्ति के साथ "देखा" गया है:

def max_unique_substrings(s, seen=()):
    return max((1 + max_unique_substrings(s[i:], {candidate, *seen}) for i in range(1, len(s) + 1) if (candidate := s[:i]) not in seen), default=0)

मैंने इस समस्या को इसके संदर्भ में एक कोशिश और सोचा है या किसी दिए गए इंडेक्स में विभाजन करना है। तो यह फ़ंक्शन पुनरावर्ती है और प्रत्येक सूचकांक पर 2 शाखाएं बनाता है। इंडेक्स में विभाजन न करें 2. इंडेक्स में विभाजन i।

विभाजन के आधार पर मैं एक सेट में भरता हूं और फिर सेट का आकार वापस करता हूं

def max(a,b):
    if a>b: return a
    return b



def keep(last, current, inp, map):
    # print last
    # print current
    # print map

    if len(inp) == 2 :
        if inp[0]==inp[1]: return 1
        return 2

    if current >= len(inp):
        return len(map)
    // This is when we are at the start of the string. 
    // In this case we can only do one thing not partition and thus take the entire string as a possible string.

    if current == last :
        map11 = map.copy()
        map11.add(inp[current:])
        return keep(last, current + 1, inp, map11)

    map1 = map.copy();
    if current != (len(inp)-1):
        map1.add(inp[last:current])

    map2 = map.copy()

    return max(keep(last,current+1,inp, map2), keep(current, current+1, inp, map1))

print keep(0,0,"121", set([]))
print keep(0,0,"aaaaaaa", set([]))
print keep(0,0,"aba", set([]))
print keep(0,0,"aababaa", set([]))
print keep(0,0,"21", set([]))
print keep(0,0,"22", set([]))

https://onlinegdb.com/HJynWw-iH


यह टकराव-जागरूक स्ट्रिंग विभाजन समस्या के रूप में जाना जाता है और ऐनी कोंडॉन, JAN Maňuch और क्रिस थाचुक द्वारा एक पेपर में 3-SAT से कमी के द्वारा एनपी-पूर्ण होना दिखाया गया है - टक्कर-जागरूक स्ट्रिंग विभाजन समस्या की जटिलता और इसके जीन संश्लेषण के लिए ओलिगो डिजाइन के संबंध में ( अंतर्राष्ट्रीय कम्प्यूटिंग और कॉम्बिनेटरिक्स सम्मेलन , 265-275, 2008)।


यहां एक समाधान है, लेकिन यह वास्तव में तेजी से बढ़ता है और एक कुशल समाधान के पास कहीं भी नहीं है। यह पहली बार ऑर्डर करने के लिए कोई चिंता नहीं के साथ अद्वितीय सबस्ट्रिंग की एक सूची में स्ट्रिंग को तोड़ता है, फिर उन सबस्ट्रिंग को मूल स्ट्रिंग में वापस इकट्ठा करने के लिए पुनरावृत्ति का उपयोग करने का प्रयास करता है, यह देखने के लिए कि यह मूल स्ट्रिंग से मेल खाता है या नहीं।

import itertools as it

def splitter(seq):                                                             
    temp = [seq]
    for x in range(1, len(seq)):
        print(seq[:x], seq[x:])
        temp.append(seq[:x])
        temp.append(seq[x:])
    return temp

if __name__ == "__main__":
    test = input("Enter a string: ")
    temp = splitter(test)
    copy = temp[::]
    condition = True
    for x in temp:
        if len(x) > 1:
            copy.extend(splitter(x))
    copy = sorted(list(set(copy)))
    print(copy)
    count = []
    for x in range(len(test)):
        item = it.permutations(copy, x)
        try:
            while True:
                temp = next(item)
                if "".join(list(temp)) == test:
                    if len(temp) == len(set(temp)):
                        count.append((len(temp), temp))
        except StopIteration:
            print('next permutation begin iteration')
            continue
    print(f"All unique splits: {count}")
    print(f"Longest unique split : {max(count)[0]}")

पहले परीक्षण के लिए हमें यह मिलता है:

All unique splits: [(1, ('aababaa',)), (2, ('a', 'ababaa')), (2, ('aa', 'babaa')), (2, 
('aab', 'abaa')), (2, ('aaba', 'baa')), (2, ('aabab', 'aa')), (2, ('aababa', 'a')), (3, 
('a', 'ab', 'abaa')), (3, ('a', 'aba', 'baa')), (3, ('a', 'abab', 'aa')), (3, ('aa', 'b',
 'abaa')), (3, ('aa', 'ba', 'baa')), (3, ('aa', 'baba', 'a')), (3, ('aab', 'a', 'baa')),
 (3, ('aab', 'ab', 'aa')), (3, ('aab', 'aba', 'a')), (3, ('aaba', 'b', 'aa')), (3,
 ('aaba', 'ba', 'a')), (4, ('a', 'aba', 'b', 'aa')), (4, ('aa', 'b', 'a', 'baa')), (4,
 ('aa', 'b', 'aba', 'a')), (4, ('aab', 'a', 'b', 'aa'))]
Longest unique split : 4

शायद इसे किसी तरह से अनुकूलित किया जा सकता है, लेकिन इस मशीन पर कुछ सेकंड लगते हैं।





algorithm