ओवरलैप

Question

के साथ स्ट्रिंग कंसटेनेशन के लिए कुशल एल्गोरिदम हमें concatenation द्वारा डेटाबेस में 3 कॉलम गठबंधन करने की आवश्यकता है। हालांकि, 3 कॉलम में ओवरलैपिंग पार्ट्स हो सकते हैं और भागों को डुप्लिकेट नहीं किया जाना चाहिए। उदाहरण के लिए,

"a" + "b" + "c" => "abc" 
    "abcde" + "defgh" + "ghlmn" => "abcdefghlmn" 
    "abcdede" + "dedefgh" + "" => "abcdedefgh" 
    "abcde" + "d" + "ghlmn" => "abcdedghlmn" 
    "abcdef" + "" + "defghl" => "abcdefghl" 

हमारे वर्तमान एल्गोरिथ्म बहुत धीमी गति से, क्योंकि यह जानवर बल का उपयोग करता है 2 तार के बीच अतिव्यापी हिस्सा पहचान करना है। क्या कोई ऐसा करने के लिए एक कुशल एल्गोरिदम जानता है?

कहते हैं कि हम 2 तार एक है और बी एल्गोरिथ्म ताकि एक एस के साथ समाप्त होता है और बी एस

जावा में हमारे वर्तमान जानवर बल लागू करने के लिए जुड़ा हुआ है के साथ शुरू होता सबसे लंबे समय तक आम-स्ट्रिंग एस खोजने के लिए की जरूरत है संदर्भ,

public static String concat(String s1, String s2) { 
    if (s1 == null) 
     return s2; 
    if (s2 == null) 
     return s1; 
    int len = Math.min(s1.length(), s2.length()); 

    // Find the index for the end of overlapping part 
    int index = -1; 
    for (int i = len; i > 0; i--) { 
     String substring = s2.substring(0, i); 
     if (s1.endsWith(substring)) { 
      index = i; 
      break; 
     } 
    } 
    StringBuilder sb = new StringBuilder(s1); 
    if (index < 0) 
     sb.append(s2); 
    else if (index <= s2.length()) 
     sb.append(s2.substring(index)); 
    return sb.toString(); 
} 

Answer 1

अन्य सभी उत्तरों ने निरंतर-कारक अनुकूलन पर ध्यान केंद्रित किया है, लेकिन यह भी असंभव रूप से बेहतर करना संभव है। अपने एल्गोरिदम को देखें: यह ओ (एन^2) है। यह एक ऐसी समस्या की तरह लगता है जिसे उससे कहीं अधिक तेज़ हल किया जा सकता है!

Knuth Morris Pratt पर विचार करें। यह अब तक पूरी तरह से मिलान किए गए सबस्ट्रिंग की अधिकतम मात्रा का ट्रैक रखता है। इसका मतलब है कि यह जानता है कि S2 के अंत में S1 का कितना मिलान से मेल खाता है, और यह वह मान है जिसे हम ढूंढ रहे हैं! जब यह सबस्ट्रिंग से शुरुआती मिलान करता है तो लौटने की बजाए जारी रखने के लिए बस एल्गोरिदम को संशोधित करें, और अंत में 0 की बजाय मिलान की गई राशि को वापस कर दें।

जो आपको एक ओ (एन) एल्गोरिदम देता है। अच्छा!

int OverlappedStringLength(string s1, string s2) { 
     //Trim s1 so it isn't longer than s2 
     if (s1.Length > s2.Length) s1 = s1.Substring(s1.Length - s2.Length); 

     int[] T = ComputeBackTrackTable(s2); //O(n) 

     int m = 0; 
     int i = 0; 
     while (m + i < s1.Length) { 
      if (s2[i] == s1[m + i]) { 
       i += 1; 
       //<-- removed the return case here, because |s1| <= |s2| 
      } else { 
       m += i - T[i]; 
       if (i > 0) i = T[i]; 
      } 
     } 

     return i; //<-- changed the return here to return characters matched 
    } 

    int[] ComputeBackTrackTable(string s) { 
     var T = new int[s.Length]; 
     int cnd = 0; 
     T[0] = -1; 
     T[1] = 0; 
     int pos = 2; 
     while (pos < s.Length) { 
      if (s[pos - 1] == s[cnd]) { 
       T[pos] = cnd + 1; 
       pos += 1; 
       cnd += 1; 
      } else if (cnd > 0) { 
       cnd = T[cnd]; 
      } else { 
       T[pos] = 0; 
       pos += 1; 
      } 
     } 

     return T; 
    } 

OverlappedStringLength ("abcdef", "defghl") रिटर्न 3

Answer 2

ऐसा क्यों न करें। पहले तीन कॉलम में पहला अक्षर या शब्द (जो ओवरलैप को इंगित करने जा रहा है) प्राप्त करें।

फिर, एक स्ट्रिंगबफर में पहली स्ट्रिंग को एक बार में जोड़ने के लिए शुरू करें।

हर बार यह देखने के लिए कि क्या आप दूसरी या तीसरी स्ट्रिंग के साथ ओवरलैप किए गए हिस्से तक पहुंच गए हैं या नहीं।

यदि ऐसा है तो स्ट्रिंग को संयोजित करना शुरू करें जिसमें पहले स्ट्रिंग में भी शामिल है।

जब कोई ओवरलैप नहीं होता है, तो दूसरी स्ट्रिंग और फिर तीसरी स्ट्रिंग के साथ शुरू करें।

तो प्रश्न में दूसरे उदाहरण में मैं दो चरों में डी और जी रखूंगा।

फिर, जैसा कि मैं पहले स्ट्रिंग एबीसी पहली स्ट्रिंग से आते हैं जोड़ने के लिए, तो मुझे लगता है कि घ दूसरी स्ट्रिंग में भी है तो मैं दूसरी स्ट्रिंग डीईएफ़ स्ट्रिंग 2 से जोड़ रहे हैं से जोड़ने के लिए शिफ्ट, तो मैं आगे बढ़ें और स्ट्रिंग के साथ खत्म करें 3.

यदि आप डेटाबेस में ऐसा कर रहे हैं तो ऐसा करने के लिए संग्रहीत प्रक्रिया का उपयोग क्यों न करें?

Answer 3

आप डेटाबेस के बाहर यह कर रहे हैं, की कोशिश पर्ल:

sub concat { 
    my($x,$y) = @_; 

    return $x if $y eq ''; 
    return $y if $x eq ''; 

    my($i) = length($x) < length($y) ? length($x) : length($y); 
    while($i > 0) { 
     if(substr($x,-$i) eq substr($y,0,$i)) { 
      return $x . substr($y,$i); 
     } 
     $i--; 
    } 
    return $x . $y; 
} 

यह बिल्कुल तुम्हारा के रूप में ही एल्गोरिदम है, मैं कर रहा हूँ बस curios अगर जावा या पर्ल तेजी ;-)

Answer 4

है आप एक डीएफए का उपयोग कर सकते हैं। उदाहरण के लिए, एक स्ट्रिंग XYZ नियमित अभिव्यक्ति ^((A)?B)?C द्वारा पढ़ा जाना चाहिए। वह नियमित अभिव्यक्ति सबसे लंबे उपसर्ग से मेल खाती है जो XYZ स्ट्रिंग के प्रत्यय से मेल खाती है। इस तरह की नियमित अभिव्यक्ति के साथ आप या तो मैच परिणाम प्राप्त कर सकते हैं और एक डीएफए उत्पन्न कर सकते हैं, जिस पर आप "कट" के लिए उचित स्थिति इंगित करने के लिए राज्य का उपयोग कर सकते हैं।

स्काला में, पहली कार्यान्वयन - सीधे regex का उपयोग कर - इस तरह जाना हो सकता है:

def toRegex(s1: String) = "^" + s1.map(_.toString).reduceLeft((a, b) => "("+a+")?"+b) r 
def concatWithoutMatch(s1 : String, s2: String) = { 
    val regex = toRegex(s1) 
    val prefix = regex findFirstIn s2 getOrElse "" 
    s1 + s2.drop(prefix length) 
} 

उदाहरण के लिए:

scala> concatWithoutMatch("abXabXabXac", "XabXacd") 
res9: java.lang.String = abXabXabXacd 

scala> concatWithoutMatch("abc", "def") 
res10: java.lang.String = abcdef 

scala> concatWithoutMatch(concatWithoutMatch("abcde", "defgh"), "ghlmn") 
res11: java.lang.String = abcdefghlmn 

Answer 5

या आप के साथ निम्न संग्रहीत mysql में यह कर सकता है समारोह:

DELIMITER // 

DROP FUNCTION IF EXISTS concat_with_overlap // 

CREATE FUNCTION concat_with_overlap(a VARCHAR(100), b VARCHAR(100)) 
    RETURNS VARCHAR(200) DETERMINISTIC 
BEGIN 
    DECLARE i INT; 
    DECLARE al INT; 
    DECLARE bl INT; 
    SET al = LENGTH(a); 
    SET bl = LENGTH(a); 
    IF al=0 THEN 
    RETURN b; 
    END IF; 
    IF bl=0 THEN 
    RETURN a; 
    END IF; 
    IF al < bl THEN 
    SET i = al; 
    ELSE 
    SET i = bl; 
    END IF; 

    search: WHILE i > 0 DO 
    IF RIGHT(a,i) = LEFT(b,i) THEN 
    RETURN CONCAT(a, SUBSTR(b,i+1)); 
    END IF; 
    SET i = i - 1; 
    END WHILE search; 

    RETURN CONCAT(a,b); 
END// 

मैं अपने परीक्षण डाटा के साथ इसे करने की कोशिश:

mysql> select a,b,c, 
    -> concat_with_overlap(concat_with_overlap(a, b), c) as result 
    -> from testing // 
+-------------+---------+--------+-------------+ 
| a   | b  | c  | result  | 
+-------------+---------+--------+-------------+ 
| a   | b  | c  | abc   | 
| abcde  | defgh | ghlmn | abcdefghlmn | 
| abcdede  | dedefgh |  | abcdedefgh | 
| abcde  | d  | ghlmn | abcdedghlmn | 
| abcdef  |   | defghl | abcdefghl | 
| abXabXabXac | XabXac |  | abXabXabXac | 
+-------------+---------+--------+-------------+ 
6 rows in set (0.00 sec) 

Answer 6

कैसे के बारे में (क्षमा सी #):

public static string OverlapConcat(string s1, string s2) 
{ 
    // Handle nulls... never return a null 
    if (string.IsNullOrEmpty(s1)) 
    { 
     if (string.IsNullOrEmpty(s2)) 
      return string.Empty; 
     else 
      return s2; 
    } 
    if (string.IsNullOrEmpty(s2)) 
     return s1; 

    // Checks above guarantee both strings have at least one character 
    int len1 = s1.Length - 1; 
    char last1 = s1[len1]; 
    char first2 = s2[0]; 

    // Find the first potential match, bounded by the length of s1 
    int indexOfLast2 = s2.LastIndexOf(last1, Math.Min(len1, s2.Length - 1)); 
    while (indexOfLast2 != -1) 
    { 
     if (s1[len1 - indexOfLast2] == first2) 
     { 
      // After the quick check, do a full check 
      int ix = indexOfLast2; 
      while ((ix != -1) && (s1[len1 - indexOfLast2 + ix] == s2[ix])) 
       ix--; 
      if (ix == -1) 
       return s1 + s2.Substring(indexOfLast2 + 1); 
     } 

     // Search for the next possible match 
     indexOfLast2 = s2.LastIndexOf(last1, indexOfLast2 - 1); 
    } 

    // No match found, so concatenate the full strings 
    return s1 + s2; 
} 

इस कार्यान्वयन नहीं है किसी भी स्ट्रिंग प्रतियां (आंशिक या अन्यथा) जब तक यह स्थापित किया है क्या नकल है, जो एक बहुत प्रदर्शन की मदद करनी चाहिए की जरूरत है।

इसके अलावा, मैच की जांच पहले संभावित मिलान वाले क्षेत्र (2 सिंगल कैरेक्टर) के चरमपंथियों का परीक्षण करती है, जो सामान्य अंग्रेजी पाठ में विसंगतियों के लिए किसी भी अन्य पात्रों की जांच से बचने का एक अच्छा मौका देना चाहिए।

केवल एक बार यह सबसे लंबा मैच स्थापित करने के बाद यह कर सकता है, या कोई भी मैच संभव नहीं है, तो दो तारों को संयोजित किया जाएगा। मैंने यहां सरल '+' का उपयोग किया है, क्योंकि मुझे लगता है कि शेष एल्गोरिदम के अनुकूलन ने आपके मूल में अधिकांश अक्षमताओं को पहले ही हटा दिया है। इसे आज़माएं और मुझे बताएं कि क्या यह आपके उद्देश्यों के लिए पर्याप्त है।

Answer 7

यहां पायथन में एक समाधान है। यह हर समय स्मृति में सबस्ट्रिंग बनाने की आवश्यकता नहीं है। काम _concat फ़ंक्शन में किया जाता है, जो दो तारों को जोड़ता है। कॉन्सट फ़ंक्शन एक सहायक है जो किसी भी स्ट्रिंग को जोड़ता है।

def concat(*args): 
    result = '' 
    for arg in args: 
     result = _concat(result, arg) 
    return result 

def _concat(a, b): 
    la = len(a) 
    lb = len(b) 
    for i in range(la): 
     j = i 
     k = 0 
     while j < la and k < lb and a[j] == b[k]: 
      j += 1 
      k += 1 
     if j == la: 
      n = k 
      break 
    else: 
     n = 0 
    return a + b[n:] 

if __name__ == '__main__': 
    assert concat('a', 'b', 'c') == 'abc' 
    assert concat('abcde', 'defgh', 'ghlmn') == 'abcdefghlmn' 
    assert concat('abcdede', 'dedefgh', '') == 'abcdedefgh' 
    assert concat('abcde', 'd', 'ghlmn') == 'abcdedghlmn' 
    assert concat('abcdef', '', 'defghl') == 'abcdefghl' 

Answer 8

मुझे लगता है कि यह बहुत जल्दी हो जाएगा:

आप दो तार, string1 और string2 है। स्ट्रिंग 2 के पहले अक्षर के लिए स्ट्रिंग 1 के माध्यम से पीछे की ओर (दाईं ओर बाएं) देखें। एक बार आपके पास यह स्थिति हो जाने के बाद, यह निर्धारित करें कि ओवरलैप है या नहीं। यदि नहीं है, तो आपको खोज रखने की आवश्यकता है। यदि आपको यह निर्धारित करने की आवश्यकता है कि किसी अन्य मैच के लिए कोई संभावना है या नहीं।

ऐसा करने के लिए, ओवरलैपिंग वर्णों के पुनरावृत्ति के लिए बस दो तारों के छोटे से एक्सप्लोर करें। यानी: यदि स्ट्रिंग 1 में मैच का स्थान एक छोटा स्ट्रिंग 1 शेष छोड़ देता है, तो स्ट्रिंग 1 में नए शुरुआती बिंदु से प्रारंभिक खोज दोहराएं। इसके विपरीत, यदि स्ट्रिंग 2 का बेजोड़ हिस्सा छोटा है, तो ओवरलैपिंग वर्णों को दोहराने के लिए इसे खोजें।

आवश्यकतानुसार दोहराना।

काम किया!

इसे मेमोरी आवंटन (सभी जगहों पर किए गए खोज, केवल परिणामस्वरूप स्ट्रिंग बफर आवंटित करने की आवश्यकता है) के मामले में बहुत अधिक आवश्यकता नहीं है और केवल स्ट्रिंग्स को ओवरलैप किए जाने वाले एक में से अधिकतर (पास) की आवश्यकता होती है।

Answer 9

मैं इस सी # को जितना संभव हो सके पढ़ने के लिए सुखद बनाने की कोशिश कर रहा हूं।

public static string Concatenate(string s1, string s2) 
    { 
     if (string.IsNullOrEmpty(s1)) return s2; 
     if (string.IsNullOrEmpty(s2)) return s1; 
     if (s1.Contains(s2)) return s1; 
     if (s2.Contains(s1)) return s2; 

     char endChar = s1.ToCharArray().Last(); 
     char startChar = s2.ToCharArray().First(); 

     int s1FirstIndexOfStartChar = s1.IndexOf(startChar); 
     int overlapLength = s1.Length - s1FirstIndexOfStartChar; 

     while (overlapLength >= 0 && s1FirstIndexOfStartChar >=0) 
     { 
      if (CheckOverlap(s1, s2, overlapLength)) 
      { 
       return s1 + s2.Substring(overlapLength); 
      } 

      s1FirstIndexOfStartChar = 
       s1.IndexOf(startChar, s1FirstIndexOfStartChar); 
      overlapLength = s1.Length - s1FirstIndexOfStartChar; 

     } 

     return s1 + s2; 
    } 

    private static bool CheckOverlap(string s1, string s2, int overlapLength) 
    { 
     if (overlapLength <= 0) 
      return false; 

     if (s1.Substring(s1.Length - overlapLength) == 
      s2.Substring(0, overlapLength)) 
      return true; 

     return false;    
    } 

संपादित करें: मुझे लगता है कि यह लगभग जेरीजेएलएल समाधान के समान है।केवल अंतर यह है कि यह "abcde", "d" केस के साथ काम करेगा।

Answer 10

यह समस्या सबसे लंबे समय तक आम उप अनुक्रम समस्या का एक परिवर्तन, गतिशील प्रोग्रामिंग के माध्यम से हल किया जा सकता है जो की तरह लगता है।

http://www.algorithmist.com/index.php/Longest_Common_Subsequence

Answer 11

उसके बारे में यहां पर्ल -pseudo oneliner:

$ _ = s1.s2;

एस/([\ एस] +) \ 1/\ 1 /;

perl regex बहुत कुशल हैं, आप देख सकते हैं कि वे किस प्रकार का उपयोग कर रहे हैं लेकिन वे निश्चित रूप से कुछ प्रकार के एफएसएम इत्यादि को लागू करते हैं, इसलिए आपको परिणाम बहुत अच्छे ओ (..) में मिलेंगे।

Answer 12

यहां जावा कार्यान्वयन है जो ओ (न्यूनतम (एन, एम)) संचालन ~ ओ (एन) जैसे कुछ में लंबाई एन और एम के साथ दो तारों के बीच अधिकतम ओवरलैप पाता है।

मेरे पास @ sepp2k: s अब हटाए गए उत्तर के समान विचार था, और इस पर थोड़ा आगे काम किया। ठीक काम करने लगता है। विचार पहली स्ट्रिंग के माध्यम से फिर से शुरू करना है और दूसरी स्ट्रिंग की शुरुआत से मेल खाने वाला कुछ खोजने के बाद ट्रैकिंग शुरू करना है। यह पता लगाया गया है कि झूठे और सच्चे मैचों ओवरलैपिंग होने पर आपको एकाधिक एक साथ ट्रैकिंग करने की आवश्यकता हो सकती है। अंत में आप सबसे लंबा ट्रैक चुनते हैं।

मैचों के बीच अधिकतम ओवरलैप के साथ, मैंने अभी तक सबसे खराब मामले का काम किया है, लेकिन मुझे उम्मीद है कि यह नियंत्रण से बाहर हो जाएगा क्योंकि मुझे लगता है कि आप मनमाने ढंग से कई मैचों को ओवरलैप नहीं कर सकते हैं। आम तौर पर आप एक समय में केवल एक या दो मैचों को ट्रैक करते हैं: जैसे ही कोई मेल नहीं होता है, उम्मीदवारों को हटा दिया जाता है।

static class Candidate { 
    int matchLen = 0; 
} 

private String overlapOnce(@NotNull final String a, @NotNull final String b) { 
    final int maxOverlap = Math.min(a.length(), b.length()); 
    final Collection<Candidate> candidates = new LinkedList<>(); 
    for (int i = a.length() - maxOverlap; i < a.length(); ++i) { 
     if (a.charAt(i) == b.charAt(0)) { 
      candidates.add(new Candidate()); 
     } 
     for (final Iterator<Candidate> it = candidates.iterator(); it.hasNext();) { 
      final Candidate candidate = it.next(); 
      if (a.charAt(i) == b.charAt(candidate.matchLen)) { 
       //advance 
       ++candidate.matchLen; 
      } else { 
       //not matching anymore, remove 
       it.remove(); 
      } 
     } 

    } 
    final int matchLen = candidates.isEmpty() ? 0 : 
      candidates.stream().map(c -> c.matchLen).max(Comparator.comparingInt(l -> l)).get(); 
    return a + b.substring(matchLen); 
} 

private String overlapOnce(@NotNull final String... strings) { 
    return Arrays.stream(strings).reduce("", this::overlapOnce); 
} 

और कुछ परीक्षण:

@Test 
public void testOverlapOnce() throws Exception { 
    assertEquals("", overlapOnce("", "")); 
    assertEquals("ab", overlapOnce("a", "b")); 
    assertEquals("abc", overlapOnce("ab", "bc")); 
    assertEquals("abcdefghqabcdefghi", overlapOnce("abcdefgh", "efghqabcdefghi")); 
    assertEquals("aaaaaabaaaaaa", overlapOnce("aaaaaab", "baaaaaa")); 
    assertEquals("ccc", overlapOnce("ccc", "ccc")); 
    assertEquals("abcabc", overlapOnce("abcabc", "abcabc")); 

    /** 
    * "a" + "b" + "c" => "abc" 
    "abcde" + "defgh" + "ghlmn" => "abcdefghlmn" 
    "abcdede" + "dedefgh" + "" => "abcdedefgh" 
    "abcde" + "d" + "ghlmn" => "abcdedghlmn" 
    "abcdef" + "" + "defghl" => "abcdefghl" 
    */ 
    assertEquals("abc", overlapOnce("a", "b", "c")); 
    assertEquals("abcdefghlmn", overlapOnce("abcde", "defgh", "ghlmn")); 
    assertEquals("abcdedefgh", overlapOnce("abcdede", "dedefgh")); 
    assertEquals("abcdedghlmn", overlapOnce("abcde", "d", "ghlmn")); 
    assertEquals("abcdefghl", overlapOnce("abcdef", "", "defghl")); 


    // Consider str1=abXabXabXac and str2=XabXac. Your approach will output abXabXabXacXabXac because by 
    // resetting j=0, it goes to far back. 
    assertEquals("abXabXabXac", overlapOnce("abXabXabXac", "XabXac")); 

    // Try to trick algo with an earlier false match overlapping with the real match 
    // - match first "aba" and miss that the last "a" is the start of the 
    // real match 
    assertEquals("ababa--", overlapOnce("ababa", "aba--")); 
}