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

Revision as of 12:09, 8 August 2023

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

एक्साम्पल

स्ट्रिंग्स 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))$ स्थान का उपयोग करता है। ^[1] डायनामिक प्रोग्रामिंग $\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)$ में समय हल किया जा सकता है। ^[2]

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

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

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

यह भी देखें

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

संदर्भ

↑ Charalampopoulos, Panagiotis; Kociumaka, Tomasz; Pissis, Solon P.; Radoszewski, Jakub (Aug 2021). Mutzel, Petra; Pagh, Rasmus; Herman, Grzegorz (eds.). सबसे लंबे सामान्य सबस्ट्रिंग के लिए तेज़ एल्गोरिदम. European Symposium on Algorithms. Leibniz International Proceedings in Informatics (LIPIcs). Vol. 204. Schloss Dagstuhl. doi:10.4230/LIPIcs.ESA.2021.30. Here: Theorem 1, p.30:2.
↑ Gusfield, Dan (1999) [1997]. Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. USA: Cambridge University Press. ISBN 0-521-58519-8.

बाहरी संबंध

[CKPR21-1] Charalampopoulos, Panagiotis; Kociumaka, Tomasz; Pissis, Solon P.; Radoszewski, Jakub (Aug 2021). Mutzel, Petra; Pagh, Rasmus; Herman, Grzegorz (eds.). सबसे लंबे सामान्य सबस्ट्रिंग के लिए तेज़ एल्गोरिदम. European Symposium on Algorithms. Leibniz International Proceedings in Informatics (LIPIcs). Vol. 204. Schloss Dagstuhl. doi:10.4230/LIPIcs.ESA.2021.30. Here: Theorem 1, p.30:2.

[Gus97-2] Gusfield, Dan (1999) [1997]. Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. USA: Cambridge University Press. ISBN 0-521-58519-8.

[1]

[2]

@@ Line 1: / Line 1: @@
 {{Wikibooks |Algorithm Implementation/Strings/Longest common substring}}
-{{Distinguish|longest common subsequence}}
+{{Distinguish|लांगेस्ट कॉमन सबसीक्वेंस}}
-[[कंप्यूटर विज्ञान]] में, दो या दो से अधिक [[सबस्ट्रिंग]]्स का एक सबसे लंबा सामान्य उपस्ट्रिंग एक सबसे लंबी [[स्ट्रिंग (कंप्यूटर विज्ञान)]] है जो उन सभी का एक उपस्ट्रिंग है। एक से अधिक सबसे लंबी सामान्य उपस्ट्रिंग हो सकती है। अनुप्रयोगों में [[डेटा डिडुप्लीकेशन]] और [[साहित्यिक चोरी का पता लगाना]] शामिल है।
+[[कंप्यूटर विज्ञान]] में, दो या दो से अधिक [[सबस्ट्रिंग]] का एक '''लांगेस्ट कॉमन सबसीक्वेंस''' एक सबसे लांगेस्ट [[स्ट्रिंग (कंप्यूटर विज्ञान)]] है जो उन सभी का एक सबस्ट्रिंग है। एक से अधिक लांगेस्ट कॉमन सबस्ट्रिंग हो सकती है। एप्लीकेशन में [[डेटा डिडुप्लीकेशन]] और [[साहित्यिक चोरी का पता लगाना|प्लगियरीसम डिटेक्शन]] इनक्लूडेड है।
-==उदाहरण==
+==एक्साम्पल==
-[[File:LongestSubstring svg.svg|thumb|स्ट्रिंग्स BADANAT और CANADAS अधिकतम-लंबाई वाले सबस्ट्रिंग्स ADA और ANA को साझा करते हैं।]]चित्र दो स्ट्रिंग दिखाता है जहां समस्या के कई समाधान हैं। हालाँकि सबस्ट्रिंग घटनाएँ हमेशा ओवरलैप होती हैं, अब उन्हें एकजुट करके सामान्य सबस्ट्रिंग प्राप्त नहीं किया जा सकता है।
+[[File:LongestSubstring svg.svg|thumb|स्ट्रिंग्स BADANAT और CANADAS मैक्सिमल-लेंथ वाले सबस्ट्रिंग्स ADA और ANA को शेयर करते हैं।]]पिक्चर दो स्ट्रिंग दिखाता है जहां प्रॉब्लम के कई सोल्यूशन हैं। हालाँकि सबस्ट्रिंग अकर्रेंस हमेशा ओवरलैप होती हैं, अब उन्हें एकजुट करके कॉमन सबस्ट्रिंग प्राप्त नहीं किया जा सकता है।
-स्ट्रिंग ABABC, BABCA और ABCBA में केवल एक सबसे लंबी उभयनिष्ठ उपस्ट्रिंग है, अर्थात। लंबाई की ABC 3. अन्य सामान्य उपस्ट्रिंग A , AB , B , BA , BC और C हैं।
+स्ट्रिंग ABABC, BABCA और ABCBA में केवल एक सबसे लांगेस्ट उभयनिष्ठ सबस्ट्रिंग है, अर्थात। लेंथ की ABC 3. अन्य कॉमन सबस्ट्रिंग A , AB , B , BA , BC और C हैं।
-   एबीएबीसी
+     ABABC
+  |||
+    BABCA
       |||
-    बाबा
+      ABCBA
-      |||
-     एबीसीबीए
-==समस्या परिभाषा==
+==प्रॉब्लम डेफिनिशन==
-दो तार दिए गए, <math>S</math> लम्बाई का <math>m</math> और <math>T</math> लम्बाई का <math>n</math>, एक सबसे लंबी स्ट्रिंग ढूंढें जो दोनों का उपस्ट्रिंग है <math>S</math> और <math>T</math>.
+दो स्ट्रिंग दिए गए, <math>S</math> लेंथ का <math>m</math> और <math>T</math> लेंथ का <math>n</math>, एक सबसे लांगेस्ट स्ट्रिंग ढूंढें जो दोनों का सबस्ट्रिंग <math>S</math> और <math>T</math> है।
-एक सामान्यीकरण k-कॉमन सबस्ट्रिंग समस्या है। तारों के सेट को देखते हुए <math>S = \{S_1, ..., S_K\}</math>, कहाँ <math>|S_i|=n_i</math> और <math>\Sigma n_i = N</math>. प्रत्येक के लिए खोजें <math>2 \leq k \leq K</math>, एक सबसे लंबी स्ट्रिंग जो कम से कम सबस्ट्रिंग के रूप में होती है <math>k</math> तार.
+एक जेनेरलाइज़ेशन k-कॉमन सबस्ट्रिंग प्रॉब्लम है। स्ट्रिंग के सेट <math>S = \{S_1, ..., S_K\}</math> को देखते हुए, जहाँ <math>|S_i|=n_i</math> और <math>\Sigma n_i = N</math> है। प्रत्येक <math>2 \leq k \leq K</math> के लिए, एक लॉन्गेस्ट स्ट्रिंग ढूंढें जो कम से कम <math>k</math> स्ट्रिंग के सबस्ट्रिंग के रूप में होती है।
 ==एल्गोरिदम==
-कोई सबसे लंबे सामान्य उपस्ट्रिंग की लंबाई और शुरुआती स्थिति का पता लगा सकता है <math>S</math> और <math>T</math> बिग ओ नोटेशन में#बैचमैन-लैंडौ नोटेशन का परिवार|<math>\Theta</math><math>(n+m)</math> [[सामान्यीकृत प्रत्यय वृक्ष]] की सहायता से समय। यदि आकार हो तो गणना के [[राम शब्द]] मॉडल में एक तेज़ एल्गोरिदम प्राप्त किया जा सकता है <math>\sigma</math> इनपुट वर्णमाला में है <math>2^{o(\sqrt{\log(n+m)})}</math>. विशेष रूप से, यह एल्गोरिथम चलता है <math>O((n+m)\log\sigma/\sqrt{\log (n+m)})</math> समय का उपयोग <math>O((n+m)\log\sigma/\log (n+m))</math> अंतरिक्ष।<ref name="CKPR21">{{cite conference | last1 = Charalampopoulos | first1 = Panagiotis | last2 = Kociumaka | first2 = Tomasz | last3 = Pissis | first3 = Solon P. | last4 = Radoszewski | first4 = Jakub | date = Aug 2021 | title = सबसे लंबे सामान्य सबस्ट्रिंग के लिए तेज़ एल्गोरिदम| conference = European Symposium on Algorithms |  editor1-last=Mutzel|editor1-first=Petra|editor2-last=Pagh|editor2-first=Rasmus|editor3-last=Herman|editor3-first=Grzegorz | publisher=Schloss Dagstuhl | series=Leibniz International Proceedings in Informatics (LIPIcs) | volume=204 | doi = 10.4230/LIPIcs.ESA.2021.30 }} Here: Theorem 1, p.30:2.</ref> [[गतिशील प्रोग्रामिंग]] लागतों द्वारा समस्या का समाधान <math>\Theta(nm)</math>. सामान्यीकृत समस्या का समाधान लेते हैं <math>\Theta(n_1 + ... + n_K)</math> अंतरिक्ष और <math>\Theta(n_1</math>·...·<math>n_K)</math> गतिशील प्रोग्रामिंग के साथ समय और ले लो <math>\Theta((n_1 + ... + n_K) * K)</math> सामान्यीकृत प्रत्यय वृक्ष के साथ समय।
+कोई सामान्यीकृत सफिक्स ट्री की सहायता से <math>\Theta</math> <math>(n+m)</math> समय में <math>S</math> और <math>T</math> के लॉन्गेस्ट कॉमन सबस्ट्रिंग की लंबाई और स्टार्टिंग पोजीशन का पता लगा सकता है। यदि <math>\sigma</math> इनपुट अल्फाबेट का आकार <math>2^{o(\sqrt{\log(n+m)})}</math> है तो कम्प्यूटेशन के वर्ड रैम मॉडल में एक फास्टर एल्गोरिदम प्राप्त किया जा सकता है। विशेष रूप से, यह एल्गोरिथम <math>O((n+m)\log\sigma/\sqrt{\log (n+m)})</math> समय <math>O((n+m)\log\sigma/\log (n+m))</math> स्थान का उपयोग करता है। <ref name="CKPR21">{{cite conference | last1 = Charalampopoulos | first1 = Panagiotis | last2 = Kociumaka | first2 = Tomasz | last3 = Pissis | first3 = Solon P. | last4 = Radoszewski | first4 = Jakub | date = Aug 2021 | title = सबसे लंबे सामान्य सबस्ट्रिंग के लिए तेज़ एल्गोरिदम| conference = European Symposium on Algorithms |  editor1-last=Mutzel|editor1-first=Petra|editor2-last=Pagh|editor2-first=Rasmus|editor3-last=Herman|editor3-first=Grzegorz | publisher=Schloss Dagstuhl | series=Leibniz International Proceedings in Informatics (LIPIcs) | volume=204 | doi = 10.4230/LIPIcs.ESA.2021.30 }} Here: Theorem 1, p.30:2.</ref> [[गतिशील प्रोग्रामिंग|डायनामिक प्रोग्रामिंग]] <math>\Theta(nm)</math> लागतों द्वारा प्रॉब्लम का सोल्यूशन होता है। जनरलाइज़्ड प्रॉब्लम का सोल्यूशन डायनामिक प्रोग्रामिंग के साथ और  <math>\Theta((n_1 + ... + n_K) * K)</math>समय जनरलाइज़्ड सफिक्स ट्री के साथ <math>\Theta(n_1 + ... + n_K)</math> स्पेस और <math>\Theta(n_1</math>·...·<math>n_K)</math> समय लेता है।
-===प्रत्यय वृक्ष===
+===सफिक्स ट्री===
-[[Image:Suffix tree ABAB BABA ABBA.svg|thumb|400px|right|स्ट्रिंग ABAB, BABA और ABBA के लिए सामान्यीकृत प्रत्यय वृक्ष, क्रमांकित 0, 1 और 2।]]स्ट्रिंग्स के एक सेट की सबसे लंबी सामान्य सबस्ट्रिंग्स को स्ट्रिंग्स के लिए एक सामान्यीकृत प्रत्यय ट्री बनाकर पाया जा सकता है, और फिर सबसे गहरे आंतरिक नोड्स को ढूंढकर, जिनमें इसके नीचे के सबट्री में सभी स्ट्रिंग्स से लीफ नोड्स होते हैं। दाईं ओर का चित्र स्ट्रिंग ABAB, BABA और ABBA के लिए प्रत्यय वृक्ष है, जो अद्वितीय स्ट्रिंग टर्मिनेटर के साथ गद्देदार है, जो ABAB$0, BABA$1 और ABBA$2 बन जाता है। ए, बी, एबी और बीए का प्रतिनिधित्व करने वाले सभी नोड्स में सभी स्ट्रिंग्स के वंशज पत्ते हैं, जिनकी संख्या 0, 1 और 2 है।
+[[Image:Suffix tree ABAB BABA ABBA.svg|thumb|400px|right|स्ट्रिंग ABAB, BABA और ABBA के लिए जनरलाइज़्ड सफिक्स ट्री, नंबर 0, 1 और 2।]]स्ट्रिंग्स के एक सेट की सबसे लांगेस्ट कॉमन सबस्ट्रिंग्स को स्ट्रिंग्स के लिए एक जनरलाइज़्ड सफिक्स ट्री बनाकर पाया जा सकता है, और फिर सबसे डीपेस्ट इंटरनल नोड्स को ढूंढकर, जिनमें इसके नीचे के सबट्री में सभी स्ट्रिंग्स से लीफ नोड्स होते हैं। राइट साइड की पिक्चर स्ट्रिंग ABAB, BABA और ABBA के लिए सफिक्स ट्री है, जो यूनिक स्ट्रिंग टर्मिनेटर के साथ पैडेड है, जो ABAB$0, BABA$1 और ABBA$2 बन जाता है। ए, बी, एबी और बीए को रिप्रेजेंट करने वाले सभी नोड्स में सभी स्ट्रिंग्स के डेस्केन्डेन्ट लीफ हैं, जिनका नंबर 0, 1 और 2 है।
-प्रत्यय वृक्ष का निर्माण होता है <math>\Theta(N)</math> समय (यदि वर्णमाला का आकार स्थिर है)। यदि पेड़ को नीचे से ऊपर तक एक बिट वेक्टर के साथ घुमाया जाता है जो बताता है कि प्रत्येक नोड के नीचे कौन सी स्ट्रिंग देखी जाती है, तो के-कॉमन सबस्ट्रिंग समस्या को हल किया जा सकता है <math>\Theta(NK)</math> समय। यदि प्रत्यय वृक्ष को निरंतर समय न्यूनतम सामान्य पूर्वज पुनर्प्राप्ति के लिए तैयार किया जाता है, तो इसे हल किया जा सकता है <math>\Theta(N)</math> समय।<ref name="Gus97">{{cite book | last = Gusfield | first = Dan | orig-year = 1997 | year = 1999 | title = Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology | publisher = Cambridge University Press | location = USA | isbn = 0-521-58519-8|url=https://books.google.com/books?id=Ofw5w1yuD8kC&q=%22longest+common+substring%22}}</ref>
+सफिक्स ट्री  <math>\Theta(N)</math> समय (यदि अल्फाबेट का आकार स्थिर है) में बिल्ट होता है। यदि ट्री को नीचे से ऊपर तक एक बिट वेक्टर के साथ घुमाया जाता है जो बताता है कि प्रत्येक नोड के नीचे कौन सी स्ट्रिंग देखी जाती है, तो के-कॉमन सबस्ट्रिंग प्रॉब्लम को <math>\Theta(NK)</math> समय में हल किया जा सकता है। यदि सफिक्स ट्री को कांस्टेंट टाइम लोवेस्ट कॉमन एनसेस्टर रिट्रीवल के लिए तैयार किया जाता है, तो इसे <math>\Theta(N)</math> में समय हल किया जा सकता है। <ref name="Gus97">{{cite book | last = Gusfield | first = Dan | orig-year = 1997 | year = 1999 | title = Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology | publisher = Cambridge University Press | location = USA | isbn = 0-521-58519-8|url=https://books.google.com/books?id=Ofw5w1yuD8kC&q=%22longest+common+substring%22}}</ref>
-===गतिशील प्रोग्रामिंग===
+===डायनामिक प्रोग्रामिंग===
-निम्नलिखित स्यूडोकोड गतिशील प्रोग्रामिंग के साथ दो स्ट्रिंग्स के बीच सबसे लंबे सामान्य सबस्ट्रिंग का सेट ढूंढता है:
+निम्नलिखित स्यूडोकोड डायनामिक प्रोग्रामिंग के साथ दो स्ट्रिंग्स के बीच लॉन्गेस्ट कॉमन सबस्ट्रिंग का सेट ढूंढता है:
+  '''function''' LongestCommonSubstring(S[1..r], T[1..n])
-  फ़ंक्शन LongestCommonSubstring(S[1..r], T[1..n])
+      L := '''array'''(1..r, 1..n)
-      एल := सरणी(1..आर, 1..एन)
+      z := 0
-      z := 0
+      ret := {}
-      ret := {}
-      i के लिए := 1..r
+      '''for''' i := 1..r
-          j के लिए := 1..n
+          '''for''' j := 1..n
-              यदि एस[आई] = टी[जे]
+              '''if''' S[i] = T[j]
-                  यदि मैं = 1 या जे = 1
+                  '''if''' i = 1 '''or''' j = 1
-                      एल[आई, जे] := 1
+                      L[i, j] := 1
-                  अन्य
+                  '''else'''
-                      एल[आई, जे] := एल[आई - 1, जे - 1] + 1
+                      L[i, j] := L[i − 1, j − 1] + 1
-                  यदि L[i, j] > z
+                  '''if''' L[i, j] > z
-                      जेड := एल[आई, जे]
+                      z := L[i, j]
-                      ret := {S[i − z + 1..i]}
+                      ret := {S[i − z + 1..i]}
-                  अन्यथा यदि L[i, j] = z
+                  '''else''' '''if''' L[i, j] = z
-                      ret := ret ∪ {S[i − z + 1..i]}
+                      ret := ret ∪ {S[i − z + 1..i]}
-              अन्य
+              '''else'''
-                  एल[आई, जे] := 0
+                  L[i, j] := 0
-      वापसी सेवानिवृत्त
+      '''return''' ret
+यह एल्गोरिदम <math>O(n r)</math> समय में चलता है। ऐरे <code>L</code> प्रीफिक्स <code>S[1..i]</code> और <code>T[1..j]</code>की सबसे लांगेस्ट कॉमन सबस्ट्रिंग की लेंथ स्टोर करता है जो क्रमश <code>i</code> और <code>j</code> पोजीशन पर समाप्त होता है। वेरिएबल <code>z</code> अब तक पाए गए लॉन्गेस्ट कॉमन सबस्ट्रिंग की लेंथ को होल्ड करने के लिए उपयोग किया जाता है। सेट <code>ret</code>  <code>z</code>लेंथ के स्ट्रिंग के सेट को होल्ड करने के लिए उपयोग किया जाता है। सेट <code>ret</code> केवल इंडेक्स <code>i</code> को सॉर्ट करके एफ्फिशिएंटली स्टोर किया जा सकता है, जो इसके स्थान पर लॉन्गेस्ट कॉमन सबस्ट्रिंग (आकार z का) का लास्ट करैक्टर <code>S[i-z+1..i]</code>है। इस प्रकार प्रत्येक i के लिए सभी लॉन्गेस्ट कॉमन सबस्ट्रिंग <code>ret</code>, <code>S[(ret[i]-z)..(ret[i])]होंगे।</code>
-यह एल्गोरिदम चलता है <math>O(n r)</math> समय। सरणी <code>L</code> उपसर्गों की सबसे लंबी सामान्य उपस्ट्रिंग की लंबाई संग्रहीत करता है <code>S[1..i]</code> और <code>T[1..j]</code> जो स्थिति पर समाप्त होता है <code>i</code> और <code>j</code>, क्रमश। परिवर्तनशील <code>z</code> अब तक पाए गए सबसे लंबे सामान्य सबस्ट्रिंग की लंबाई को पकड़ने के लिए उपयोग किया जाता है। सेट <code>ret</code> लंबाई के तारों के सेट को पकड़ने के लिए उपयोग किया जाता है <code>z</code>. सेट <code>ret</code> केवल सूचकांक को संग्रहित करके कुशलतापूर्वक सहेजा जा सकता है <code>i</code>, जो इसके बजाय सबसे लंबे सामान्य सबस्ट्रिंग (आकार z का) का अंतिम वर्ण है <code>S[i-z+1..i]</code>. इस प्रकार प्रत्येक i के लिए सभी सबसे लंबे सामान्य उपस्ट्रिंग होंगे <code>ret</code>, <code>S[(ret[i]-z)..(ret[i])]</code>.
-कार्यान्वयन के मेमोरी उपयोग को कम करने के लिए निम्नलिखित युक्तियों का उपयोग किया जा सकता है:
+इम्प्लीमेंटेशन के मेमोरी उपयोग को कम करने के लिए निम्नलिखित ट्रिक्स का उपयोग किया जा सकता है:
-* मेमोरी बचाने के लिए DP तालिका की केवल अंतिम और वर्तमान पंक्ति रखें (<math>O(\min(r, n))</math> के बजाय <math>O(n r)</math>)
+* मेमोरी (<math>O(\min(r, n))</math> के स्थान पर <math>O(n r)</math>) बचाने के लिए DP तालिका की केवल लास्ट और करंट रो रखें
-** आंतरिक लूप को पीछे की ओर घुमाकर अंतिम और वर्तमान पंक्ति को उसी 1D सरणी पर संग्रहीत किया जा सकता है
+** इनर लूप को पीछे की ओर घुमाकर लास्ट और करंट पंक्ति को उसी 1D ऐरे पर स्टोर किया जा सकता है
-* पंक्तियों में केवल गैर-शून्य मान संग्रहीत करें। यह सरणियों के बजाय हैश-टेबल का उपयोग करके किया जा सकता है। यह बड़े अक्षरों के लिए उपयोगी है.
+* रो में केवल नॉन-जीरो वैल्यू स्टोर करें। यह ऐरे के स्थान पर हैश-टेबल का उपयोग करके किया जा सकता है। यह लार्ज अल्फाबेट के लिए उपयोगी है।
 ==यह भी देखें==
-* सबसे [[सबसे लंबी पैलिंड्रोमिक सबस्ट्रिंग]]
+* [[सबसे लंबी पैलिंड्रोमिक सबस्ट्रिंग|लांगेस्ट पलिन्ड्रोमिक सबस्ट्रिंग]]
-* एन-ग्राम|एन-ग्राम, लंबाई एन के सभी संभावित सबस्ट्रिंग जो एक स्ट्रिंग में समाहित हैं
+* एन-ग्राम, लेंथ एन के सभी पॉसिबल सबस्ट्रिंग जो एक स्ट्रिंग में कन्टेनड हैं
 ==संदर्भ==

v t e Strings
String metric	Approximate string matching Bitap algorithm Damerau–Levenshtein distance Edit distance Gestalt Pattern Matching Hamming distance Jaro–Winkler distance Lee distance Levenshtein automaton Levenshtein distance Wagner–Fischer algorithm
String-searching algorithm	Apostolico–Giancarlo algorithm Boyer–Moore string-search algorithm Boyer–Moore–Horspool algorithm Knuth–Morris–Pratt algorithm Rabin–Karp algorithm
Multiple string searching	Aho–Corasick Commentz-Walter algorithm
Regular expression	Comparison of regular-expression engines Regular grammar Thompson's construction Nondeterministic finite automaton
Sequence alignment	Hirschberg's algorithm Needleman–Wunsch algorithm Smith–Waterman algorithm
Data structure	DAFSA Suffix array Suffix automaton Suffix tree Generalized suffix tree Rope Ternary search tree Trie
Other	Parsing Pattern matching Compressed pattern matching Longest common subsequence Longest common substring Sequential pattern mining Sorting

Anonymous

Search

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

Namespaces

More

Page actions

Revision as of 12:09, 8 August 2023

Contents

एक्साम्पल

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

एल्गोरिदम

सफिक्स ट्री

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

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Revision as of 12:09, 8 August 2023

एक्साम्पल

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

एल्गोरिदम

सफिक्स ट्री

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

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories