檢查兩個字符串的順序是否相同

Question

如何在javascript中編寫函數以返回兩個字符串之間共享的字母數量（按順序）。

例如：如果兩個字符串read和bread，它應該返回4.

我想使用循環莫名其妙的，但現在看來，這將是非常令人費解了很多迭代的，我不知道從哪裏開始。

有沒有辦法實現這個使用正則表達式？可能，得到匹配的子字符串？長度然後可以從substring.length

Answer 1

最長公共子串問題的algorithm是棘手的。我認爲沒有一種簡單的方法可以用正則表達式來實現。

Answer 2

我想我會做的是：

1. 查找與兩個字符串
2. 對於每一個這種的字符集，找到角色的每個實例的最長匹配串

尋找共同的字符將只是一個線性通過每個字符串，建設集，然後相交集。它不僅有助於跟蹤字符，而且還能跟蹤索引（字符串中的位置）。這樣，當你做第二部分時，你不必搜索字符串來再次找到角色。

請不要爲此投票;等到有人更聰明的時候給它一個嘗試:-)（當然，你可以投我一票。）

Here is a jsfiddle帶有一個實現。下面是執行這項工作的JavaScript函數：

function longestSharedSequence(str1, str2) { 
    var seqs = { 
     longest: null, 
     all: [] 
    }; 

    function setOfChars(s) { 
     var rv = {}, 
      c; 
     for (var i = 0; i < s.length; ++i) { 
      c = s[i]; 
      if (rv[c]) rv[c].push(i); 
      else rv[c] = [i]; 
     } 
     return rv; 
    } 

    function intersect(set1, set2) { 
     var rv = {}; 
     for (var c in set1) { 
      if (set1.hasOwnProperty(c) && set2.hasOwnProperty(c)) { 
       rv[c] = [set1[c], set2[c]]; 
      } 
     } 
     return rv; 
    } 

    function getSeq(pos1, pos2) { 
     var seq = [str1[pos1]], 
      i, j; 
     for (i = pos1 + 1, j = pos2 + 1; i < str1.length && j < str2.length && str1[i] === str2[j]; ++i, ++j) 
     seq.push(str1[i]); 
     return seq.join(''); 
    } 

    function getSeqs(positions) { 
     var i, j, p1 = positions[0], 
      p2 = positions[1], 
      seq; 
     for (i = 0; i < p1.length; ++i) { 
      for (j = 0; j < p2.length; ++j) { 
       seq = getSeq(p1[i], p2[j]); 
       seqs.all.push(seq); 
       if (seqs.longest === null || seq.length > seqs.longest.length) { 
        seqs.longest = seq; 
       } 
      } 
     } 
    } 

    var set = intersect(setOfChars(str1), setOfChars(str2)); 

    for (var c in set) { 
     if (set.hasOwnProperty(c)) { 
      getSeqs(set[c]); 
     } 
    } 

    return seqs.longest; 
} 

Answer 3

REGEX無法輕鬆完成。你應該使用嵌套循環。

See this example

在這個例子中使用的代碼：

function similarity(str1, str2) { 
    count = 0; 
    for (i = 0; i < str1.length; i++) { //Loop through the letters of the first string 
     for (j = i+1; j <= str1.length; j++) { //Loop through the letters of the first string, starting from the letter in i. 
      sub = str1.substring(i, j); //Slice the first string from i to j. 
      //console.log(sub, count, str2.indexOf(sub), j, i); 
      if (str2.indexOf(sub) != -1) { //If the sliced string is found in the second string 
       if (count < sub.length) { //If the count I currently have is lower then the current match I found 
        count = sub.length; 
       } 
      } 
     } 
    } 
    return count; 
} 
alert(similarity('zzomg', 'omg')); 

有沒有那麼多的迭代，因爲我以爲。有n+(n-1)+n(n-2)+... = n^2-n它應該沒有歇斯底里的字符串（如50個字母）罰款。

Answer 4

正則表達式的免費版本

chaine1 = "bread"; 
chaine2 = "read"; 
if(chaine1.length <= chaine2.length){ 
    count = chaine1.length; 
} 
else{ 
    count = chaine2.length; 

} 

var numberOfCharacterMatching = 0; 

for (var i =0; i<count; i++){ 
if(chaine1.charAt(i) == chaine1.charAt(i)){ 
numberOfCharacterMatching++ 
} 

} 
alert(numberOfCharacterMatching++); 

Answer 5

您應該使用其他算法答案之一。

這就是說，這裏是一個正則表達式驅動的解決方案，只是爲了好玩。在Perl中爲了方便而實現，相同的表達式可以在JavaScript中工作。

sub longest_common_substr_len{ 
    my $s = "$_[0]|$_[1]"; 
    my $l = 0; 

    $l = length > $l? length: $l for $s =~ /(?=([^|]+)(?=[^|]*\|[^|]*\1))./g; 

    return $l; 
} 

正則表達式查找所有*共同子串，並且循環獲得的最大長度。

它通過將兩個字符串連接到一個特殊的分隔符（在這種情況下不能出現在字符串中，|），然後使用正則表達式來查找（「本地最長」）子字符串（在每個字符處）在分隔符之前和之後。

外部超前封裝用於一次只推進一個字符。沒有它，「zomg」和「zoomg」只會給2，因爲「zomg」中的「zo」已經被使用而不允許「omg」匹配。

Example usage：

say longest_common_substr_len "read", "bread"; 
say longest_common_substr_len "omgzomg", "omgomg"; 
say longest_common_substr_len "zomg", "zoomg"; 

輸出：

4 
3 
3 

Answer 6

function longSubstrings(s1, s2, wbr, casesense){ 
    var temp= '', long= [], tem, tem2, str1, str2, len= 2, ax, L, i= 0; 
    if(s1.length<s2.length){ 
     tem= s1; 
     s1= s2; 
     s2= tem; 
    } 
    // whole words match faster, if appropriate: 
    wbr= wbr? ' ':''; 
    // you can force a case sensitive match: 
    str1= !casesense? s1.toLowerCase():s1; 
    str2= !casesense? s2.toLowerCase():s2; 

    // normalize spaces: 
    str1= str1.replace(/ {2,}/g, ' '); 

    str2= str2.replace(/ {2,}/g, ' '); 
    if(str1.indexOf(str2)!= -1) return s2; 
    str1= str1.split(wbr); 
    L= str1.length; 
    while(i<L){ 
     tem= tem2= str1[i]; 
     ax= str2.indexOf(tem); 
     while(ax!= -1){ 
      ++i; 
      if(tem2.length>= len){ 
       len= tem2.length; 
       long= long.filter(function(itm){ 
        return itm.length>= len; 
       }); 
       long.push(tem2); 
      } 
      tem2+= wbr+str1[i]; 
      ax= str2.indexOf(tem2); 
     } 
     ++i; 
    } 
    return long; 
} 
var s1= 'oie ja s a n y t nc eedjib n ife ks aio m io gna red dogext x ia a dso zcq a a w eadz tie s matsa fw t seno e se pi iz t s j sv b n is t h toa p q osrf o tj e s ine to e io no xo sss jfytai oooic v puieo nnoveya ktnxk atl endtan uiu n s i enhro a a w k s s nlno iai ouex a t pals tnshp ia ais ga dnog rewen z ia bs t bbnn yeq sviiaio tto qe tnoimetn ntsoei i nsut oteh r iynnw ee gos moemtehlt k az q ri svft sc oot naagtc asste nl'; 
var s2= 'q meael a n o oia d fntqss ne assto nxs n y nx aoeog pho ev t n ao ste o it eoshi j aii x s infs g a il nho t alj ot isw ic ae si k oorateaw ts iug t b oi tn i m e vnos ss o jtn enoik kaon zseeaaitialsu ej a in ays t a nzyv m ibst sxuse t l eto od zs e y os zvinaieks w wq to ce ia ufs v k mrz e n taen d endtbatn tpteiu f gx hboati m o iieac op nef t atyno n p iatb cqaicsn d tt po r oae n n gsq nrne oe ij red doga st eowsiie snhr'; 



    longSubstrings(s1, s2); 
    //checks by character 
    // returned value: (Array) 
    red dog 

    longSubstrings(s1, s2, 1); 
    //checks whole words 
    //returned value: (Array) 
    red 


// Older browsers need a shim for the filter method. 
(or just write a loop for the filter) 

if(![].filter){ 

     Array.prototype.filter= function(fun, scope){ 
      var T= this, A= [], i= 0, itm, L= T.length; 
      if(typeof fun== 'function'){ 
       while(i< L){ 
        if(i in T){ 
         itm= T[i]; 
         if(fun.call(scope, itm, i, T)) A[A.length]= itm; 
        } 
        ++i; 
       } 
      } 
      return A; 
     } 
    }