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

{{Wikibooks |Algorithm Implementation/Strings/Longest common substring}}
{{Distinguish|लांगेस्ट कॉमन सबसीक्वेंस}}
[[कंप्यूटर विज्ञान]] में, दो या दो से अधिक [[सबस्ट्रिंग]] का एक '''लांगेस्ट कॉमन सबसीक्वेंस''' एक सबसे लांगेस्ट [[स्ट्रिंग (कंप्यूटर विज्ञान)]] है जो उन सभी का एक सबस्ट्रिंग है। एक से अधिक लांगेस्ट कॉमन सबस्ट्रिंग हो सकती है। एप्लीकेशन में [[डेटा डिडुप्लीकेशन]] और [[साहित्यिक चोरी का पता लगाना|प्लगियरीसम डिटेक्शन]] इनक्लूडेड है।

==एक्साम्पल==
[[File:LongestSubstring svg.svg|thumb|स्ट्रिंग्स BADANAT और CANADAS मैक्सिमल-लेंथ वाले सबस्ट्रिंग्स ADA और ANA को शेयर करते हैं।]]पिक्चर दो स्ट्रिंग दिखाता है जहां प्रॉब्लम के कई सोल्यूशन हैं। हालाँकि सबस्ट्रिंग अकर्रेंस हमेशा ओवरलैप होती हैं, अब उन्हें एकजुट करके कॉमन सबस्ट्रिंग प्राप्त नहीं किया जा सकता है।

स्ट्रिंग 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> है। 

एक जेनेरलाइज़ेशन 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>\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 है।

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

==यह भी देखें==
* [[सबसे लंबी पैलिंड्रोमिक सबस्ट्रिंग|लांगेस्ट पलिन्ड्रोमिक सबस्ट्रिंग]]
* एन-ग्राम, लेंथ एन के सभी पॉसिबल सबस्ट्रिंग जो एक स्ट्रिंग में कन्टेनड हैं

==संदर्भ==
<references />


==बाहरी संबंध==
{{Wikibooks|Algorithm implementation|Strings/Longest common substring|Longest common substring}}
* [http://nist.gov/dads/HTML/longestCommonSubstring.html Dictionary of Algorithms and Data Structures: longest common substring]
* [http://metacpan.org/module/String::LCSS_XS Perl/XS implementation of the dynamic programming algorithm]
* [http://metacpan.org/module/Tree::Suffix Perl/XS implementation of the suffix tree algorithm]
* [[b:Algorithm implementation/Strings/Longest common substring|Dynamic programming implementations in various languages on wikibooks]]
* [http://www.emanueleferonato.com/2010/12/01/solving-the-longest-common-substring-problem-with-as3/ working AS3 implementation of the dynamic programming algorithm]
* [http://www.geeksforgeeks.org/suffix-tree-application-5-longest-common-substring-2/ Suffix Tree based C implementation of Longest common substring for two strings]

{{Strings |state=collapsed}}

[[Category:Articles with hatnote templates targeting a nonexistent page]]
[[Category:Collapse templates]]
[[Category:Created On 25/07/2023]]
[[Category:Machine Translated Page]]
[[Category:Navigational boxes| ]]
[[Category:Navigational boxes without horizontal lists]]
[[Category:Pages with script errors]]
[[Category:Sidebars with styles needing conversion]]
[[Category:Template documentation pages|Documentation/doc]]
[[Category:Templates Vigyan Ready]]
[[Category:Templates generating microformats]]
[[Category:Templates that are not mobile friendly]]
[[Category:Templates using TemplateData]]
[[Category:Wikipedia metatemplates]]
[[Category:गतिशील प्रोग्रामिंग]]
[[Category:तारों पर समस्याएँ]]
[[Category:स्यूडोकोड उदाहरण सहित लेख]]