检查两个字符串的顺序是否相同

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; 
     } 
    }