भरे गए सेल
मेल खाते जोड़े
अब तक सबसे लंबा

  • भरा जा रहा है
  • यहाँ से पढ़ा
  • उत्तर

सबसे लंबे सामान्य उपअनुक्रम के बारे में और

सबसे लंबा सामान्य उपअनुक्रम (LCS)

दो शब्दों में कौन-से अक्षर एक ही क्रम में साझा हैं? सबसे लंबा सामान्य उपअनुक्रम इसी का उत्तर देता है, और diff टूल, स्पेल चेकर और DNA तुलना इसी पर आधारित हैं। दो शब्द लिखें, उनके अक्षरों की तालिका भरते देखें, फिर कोने से उत्तर को पीछे की ओर खोजें। तालिका को भरते देखने के लिए “चलाएँ” दबाएँ, या एक-एक चरण चलने के लिए “आगे” और “पीछे” दबाएँ। कहीं भी जाने के लिए चरण स्लाइडर खींचें। दो शब्द लिखें: पहला तालिका के बगल में ऊपर से नीचे लिखा जाता है, दूसरा ऊपर की ओर बाएँ से दाएँ। हर सेल में उसकी पंक्ति और कॉलम तक के अक्षरों के सबसे लंबे सामान्य उपअनुक्रम की लंबाई होती है। अंत में अक्षर नीचे दाएँ वाले सेल से उल्टे क्रम में पढ़े जाते हैं। “नया उदाहरण” शब्दों की एक और जोड़ी चुनता है। बोर्ड चुना होने पर, ऐरो कुंजियाँ एक चरण चलाती हैं, स्पेस बार चलाता और रोकता है, और Home और End शुरुआत और अंत पर ले जाते हैं।

यह कैसे काम करता है

  1. दो शब्द लिखें: पहला तालिका के बगल में ऊपर से नीचे लिखा जाता है, दूसरा ऊपर की ओर बाएँ से दाएँ।
  2. “चलाएँ” दबाएँ, या एक-एक चरण चलने के लिए “आगे” और “पीछे” का उपयोग करें। कहीं भी जाने के लिए चरण स्लाइडर खींचें।
  3. हर सेल को अपने दो अक्षरों की तुलना करते देखें, फिर उत्तर पढ़ने के लिए नारंगी रास्ते पर कोने से पीछे की ओर चलें।

तालिका कैसे काम करती है

एक सेल में पहले शब्द के उसकी पंक्ति तक के अक्षरों और दूसरे शब्द के उसके कॉलम तक के अक्षरों के सबसे लंबे सामान्य उपअनुक्रम की लंबाई होती है। – से चिह्नित पंक्ति और कॉलम खाली शब्द दर्शाते हैं, इसलिए वे 0 हैं। अगर सेल के दोनों अक्षर बराबर हों, तो सेल ऊपर-बाएँ वाले सेल से एक अधिक होता है। अगर वे अलग हों, तो दोनों में से एक अक्षर उत्तर का हिस्सा नहीं है, इसलिए सेल ऊपर वाले और बाएँ वाले सेल में से बड़ा मान लेता है।

अक्षरों को उल्टा पढ़ना

नीचे दाएँ वाला सेल उत्तर की लंबाई है। अक्षर खोजने के लिए वहीं से शुरू करें: जहाँ दोनों अक्षर मेल खाते हैं, वह अक्षर उपअनुक्रम में है, और आप ऊपर-बाएँ जाते हैं; नहीं तो आप ऊपर वाले और बाएँ वाले सेल में से बड़े वाले पर जाते हैं। रास्ते में इकट्ठा किए गए अक्षर, उल्टे क्रम में पढ़ने पर, एक सबसे लंबा सामान्य उपअनुक्रम बनाते हैं। इतनी ही लंबाई के दूसरे भी हो सकते हैं; उल्टा पढ़ना उनमें से एक को खोजता है।

अक्सर पूछे जाने वाले प्रश्न

उपअनुक्रम और सबस्ट्रिंग में क्या अंतर है?

सबस्ट्रिंग एक-दूसरे के बगल में आने वाले अक्षरों का सिलसिला है, जैसे RACER में ACE। उपअनुक्रम क्रम बनाए रखता है लेकिन अक्षर छोड़ सकता है, इसलिए ACE, ABCDE का भी उपअनुक्रम है। सबसे लंबी सामान्य सबस्ट्रिंग एक अलग समस्या है, जिसकी तालिका मिलती-जुलती है।

LCS एल्गोरिदम कितना तेज़ है?

m और n लंबाई के शब्दों के लिए तालिका में m·n सेल होते हैं, और हर सेल एक चरण में भरता है, इसलिए काम O(m·n) है। 10,000 लाइनों वाले दो टेक्स्ट के लिए यह 10 करोड़ सेल हैं, इसीलिए diff टूल इसी विचार पर बने ज़्यादा चतुर तरीके इस्तेमाल करते हैं।

क्या सबसे लंबा सामान्य उपअनुक्रम अद्वितीय होता है?

नहीं। ABCBDAB और BDCABA के लंबाई 4 वाले तीन अलग सामान्य उपअनुक्रम हैं: BCBA, BCAB और BDAB। तालिका लंबाई बताती है; उल्टा पढ़ना उनमें से एक चुनता है।

क्या LCS बताता है कि दो शब्द कितने मिलते-जुलते हैं?

कुछ हद तक। m और n लंबाई के दो शब्द, जिनका सबसे लंबा सामान्य उपअनुक्रम k लंबाई का है, m − k अक्षर हटाकर और n − k अक्षर जोड़कर एक-दूसरे में बदले जा सकते हैं। एडिट डिस्टेंस, जिसमें अक्षर बदलने की भी अनुमति है, अक्सर बेहतर पैमाना होता है।

क्या कुछ कहीं भेजा जाता है?

नहीं। सारी गणना आपके ब्राउज़र में ही होती है, और आपकी पिछली सेटिंग्स इसी ब्राउज़र के लोकल स्टोरेज में रहती हैं।

आज़माने के लिए तैयार?

अपने ब्राउज़र में PictorX खोलें — शुरू करने के लिए इंस्टॉल या क्रेडिट कार्ड की ज़रूरत नहीं।

एडिटर पर जाएँ