दीर्घ सामान्य उपरज्जु (लांगेस्ट कॉमन सबस्ट्रिंग)

Not to be confused with लांगेस्ट कॉमन सबसीक्वेंस.

कंप्यूटर विज्ञान में, दो या दो से अधिक सबस्ट्रिंग का एक लांगेस्ट कॉमन सबसीक्वेंस एक सबसे लांगेस्ट स्ट्रिंग (कंप्यूटर विज्ञान) है जो उन सभी का एक सबस्ट्रिंग है। एक से अधिक लांगेस्ट कॉमन सबस्ट्रिंग हो सकती है। एप्लीकेशन में डेटा डिडुप्लीकेशन और प्लगियरीसम डिटेक्शन इनक्लूडेड है।

एक्साम्पल

स्ट्रिंग्स BADANAT और CANADAS मैक्सिमल-लेंथ वाले सबस्ट्रिंग्स ADA और ANA को शेयर करते हैं।

पिक्चर दो स्ट्रिंग दिखाता है जहां प्रॉब्लम के कई सोल्यूशन हैं। हालाँकि सबस्ट्रिंग अकर्रेंस हमेशा ओवरलैप होती हैं, अब उन्हें एकजुट करके कॉमन सबस्ट्रिंग प्राप्त नहीं किया जा सकता है।

स्ट्रिंग ABABC, BABCA और ABCBA में केवल एक सबसे लांगेस्ट उभयनिष्ठ सबस्ट्रिंग है, अर्थात। लेंथ की ABC 3. अन्य कॉमन सबस्ट्रिंग A , AB , B , BA , BC और C हैं।

    ABABC

 |||
   BABCA
    |||
    ABCBA

प्रॉब्लम डेफिनिशन

दो स्ट्रिंग दिए गए, $S$ लेंथ का $m$ और $T$ लेंथ का $n$, एक सबसे लांगेस्ट स्ट्रिंग ढूंढें जो दोनों का सबस्ट्रिंग $S$ और $T$ है।

एक जेनेरलाइज़ेशन k-कॉमन सबस्ट्रिंग प्रॉब्लम है। स्ट्रिंग के सेट $S=\{S_{1},...,S_{K}\}$ को देखते हुए, जहाँ $|S_{i}|=n_{i}$ और $\Sigma n_{i}=N$ है। प्रत्येक $2\leq k\leq K$ के लिए, एक लॉन्गेस्ट स्ट्रिंग ढूंढें जो कम से कम $k$ स्ट्रिंग के सबस्ट्रिंग के रूप में होती है।

एल्गोरिदम

कोई सामान्यीकृत सफिक्स ट्री की सहायता से $\Theta$ $(n+m)$ समय में $S$ और $T$ के लॉन्गेस्ट कॉमन सबस्ट्रिंग की लंबाई और स्टार्टिंग पोजीशन का पता लगा सकता है। यदि $\sigma$ इनपुट अल्फाबेट का आकार $2^{o({\sqrt {\log(n+m)}})}$ है तो कम्प्यूटेशन के वर्ड रैम मॉडल में एक फास्टर एल्गोरिदम प्राप्त किया जा सकता है। विशेष रूप से, यह एल्गोरिथम $O((n+m)\log \sigma /{\sqrt {\log(n+m)}})$ समय $O((n+m)\log \sigma /\log(n+m))$ स्थान का उपयोग करता है। डायनामिक प्रोग्रामिंग $\Theta (nm)$ लागतों द्वारा प्रॉब्लम का सोल्यूशन होता है। जनरलाइज़्ड प्रॉब्लम का सोल्यूशन डायनामिक प्रोग्रामिंग के साथ और $\Theta ((n_{1}+...+n_{K})*K)$समय जनरलाइज़्ड सफिक्स ट्री के साथ $\Theta (n_{1}+...+n_{K})$ स्पेस और $\Theta (n_{1}$·...·$n_{K})$ समय लेता है।

सफिक्स ट्री

स्ट्रिंग ABAB, BABA और ABBA के लिए जनरलाइज़्ड सफिक्स ट्री, नंबर 0, 1 और 2।

स्ट्रिंग्स के एक सेट की सबसे लांगेस्ट कॉमन सबस्ट्रिंग्स को स्ट्रिंग्स के लिए एक जनरलाइज़्ड सफिक्स ट्री बनाकर पाया जा सकता है, और फिर सबसे डीपेस्ट इंटरनल नोड्स को ढूंढकर, जिनमें इसके नीचे के सबट्री में सभी स्ट्रिंग्स से लीफ नोड्स होते हैं। राइट साइड की पिक्चर स्ट्रिंग ABAB, BABA और ABBA के लिए सफिक्स ट्री है, जो यूनिक स्ट्रिंग टर्मिनेटर के साथ पैडेड है, जो ABAB$0, BABA$1 और ABBA$2 बन जाता है। ए, बी, एबी और बीए को रिप्रेजेंट करने वाले सभी नोड्स में सभी स्ट्रिंग्स के डेस्केन्डेन्ट लीफ हैं, जिनका नंबर 0, 1 और 2 है।

सफिक्स ट्री $\Theta (N)$ समय (यदि अल्फाबेट का आकार स्थिर है) में बिल्ट होता है। यदि ट्री को नीचे से ऊपर तक एक बिट वेक्टर के साथ घुमाया जाता है जो बताता है कि प्रत्येक नोड के नीचे कौन सी स्ट्रिंग देखी जाती है, तो के-कॉमन सबस्ट्रिंग प्रॉब्लम को $\Theta (NK)$ समय में हल किया जा सकता है। यदि सफिक्स ट्री को कांस्टेंट टाइम लोवेस्ट कॉमन एनसेस्टर रिट्रीवल के लिए तैयार किया जाता है, तो इसे $\Theta (N)$ में समय हल किया जा सकता है।

डायनामिक प्रोग्रामिंग

निम्नलिखित स्यूडोकोड डायनामिक प्रोग्रामिंग के साथ दो स्ट्रिंग्स के बीच लॉन्गेस्ट कॉमन सबस्ट्रिंग का सेट ढूंढता है:

function LongestCommonSubstring(S[1..r], T[1..n])
    L := array(1..r, 1..n)
    z := 0
    ret := {}

    for i := 1..r
        for j := 1..n
            if S[i] = T[j]
                if i = 1 or j = 1
                    L[i, j] := 1
                else
                    L[i, j] := L[i − 1, j − 1] + 1
                if L[i, j] > z
                    z := L[i, j]
                    ret := {S[i − z + 1..i]}
                else if L[i, j] = z
                    ret := ret ∪ {S[i − z + 1..i]}
            else
                L[i, j] := 0
    return ret

यह एल्गोरिदम $O(nr)$ समय में चलता है। ऐरे L प्रीफिक्स S[1..i] और T[1..j]की सबसे लांगेस्ट कॉमन सबस्ट्रिंग की लेंथ स्टोर करता है जो क्रमश i और j पोजीशन पर समाप्त होता है। वेरिएबल z अब तक पाए गए लॉन्गेस्ट कॉमन सबस्ट्रिंग की लेंथ को होल्ड करने के लिए उपयोग किया जाता है। सेट ret zलेंथ के स्ट्रिंग के सेट को होल्ड करने के लिए उपयोग किया जाता है। सेट ret केवल इंडेक्स i को सॉर्ट करके एफ्फिशिएंटली स्टोर किया जा सकता है, जो इसके स्थान पर लॉन्गेस्ट कॉमन सबस्ट्रिंग (आकार z का) का लास्ट करैक्टर S[i-z+1..i]है। इस प्रकार प्रत्येक i के लिए सभी लॉन्गेस्ट कॉमन सबस्ट्रिंग ret, S[(ret[i]-z)..(ret[i])]होंगे।

इम्प्लीमेंटेशन के मेमोरी उपयोग को कम करने के लिए निम्नलिखित ट्रिक्स का उपयोग किया जा सकता है:

• मेमोरी ($O(\min(r,n))$ के स्थान पर $O(nr)$) बचाने के लिए DP तालिका की केवल लास्ट और करंट रो रखें
  • इनर लूप को पीछे की ओर घुमाकर लास्ट और करंट पंक्ति को उसी 1D ऐरे पर स्टोर किया जा सकता है
• रो में केवल नॉन-जीरो वैल्यू स्टोर करें। यह ऐरे के स्थान पर हैश-टेबल का उपयोग करके किया जा सकता है। यह लार्ज अल्फाबेट के लिए उपयोगी है।

यह भी देखें

• लांगेस्ट पलिन्ड्रोमिक सबस्ट्रिंग
• एन-ग्राम, लेंथ एन के सभी पॉसिबल सबस्ट्रिंग जो एक स्ट्रिंग में कन्टेनड हैं

बाहरी संबंध

• Dictionary of Algorithms and Data Structures: longest common substring
• Perl/XS implementation of the dynamic programming algorithm
• Perl/XS implementation of the suffix tree algorithm
• Dynamic programming implementations in various languages on wikibooks
• working AS3 implementation of the dynamic programming algorithm
• Suffix Tree based C implementation of Longest common substring for two strings