두 문자열이 같은 문자를 가지고 있는지 확인하십시오.

Question

두 문자열간에 공유되는 문자 수를 반환하는 함수를 javascript로 작성하는 방법 (순서대로).

예 : 두 문자열이 read 및 bread 경우, 내가 어떻게 든 루프를 사용하여 생각하고 4.

를 반환해야하지만, 반복이 많은 매우 복잡한 것 같다, 그리고 난 어디서부터 시작해야할지 모르겠다.

정규 표현식을 사용하여이를 달성 할 수있는 방법이 있습니까? 가능하면, 일치하는 부분 문자열을 얻으시겠습니까? 길이는 다음으로부터 도출 될 수 있습니다. substring.length

Answer 1

가장 긴 일반 하위 문자열 문제에 대한 algorithm은 다소 까다 롭습니다. 나는 쉬운 방법이 정규식과 동등한 일을한다고 생각하지 않는다.

Answer 2

은 내가 어떻게 할 것인지가있을 거라고 생각 :

1. 는 두 문자열 그 각각에 대해
2. 에있는 문자 집합을 찾아 문자의 각 인스턴스에 대한 가장 긴 일치하는 하위 문자열을 찾을 수

공통적으로 문자를 찾는 것은 각 문자열을 통과하고 세트를 만들고 그 세트를 교차하는 것입니다. 문자뿐 아니라 색인 (문자열의 위치)을 추적하는 데 도움이됩니다. 그렇게하면 두 번째 부분을 할 때 문자열을 검색하여 문자를 다시 찾을 필요가 없습니다.

아직 투표하지 마십시오. 똑똑한 사람이 시험해 볼 때까지 기다리십시오 :-) (글쎄, 당연히 나를 투표 할 수 있습니다.)

Here is a jsfiddle 구현. 그것은 REGEX 쉽게 할 수없는

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

다음은 작업을 수행하는 자바 스크립트 함수입니다. 중첩 루프를 사용해야합니다.

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

정규식은 모든 * 공통 부분 문자열을 찾고 루프는 최대 길이를 얻습니다.

두 문자열을 특별한 구분 기호 (이 경우에는 | 문자열에는 존재할 수 없음)와 연결 한 다음 정규식을 사용하여 두 문자열 인 (모든 char에서) 부분 문자열을 찾습니다 구분 기호 앞과 뒤에.

외부 lookahead 캡슐화는 한 번에 하나의 char 만 진행시키는 데 사용됩니다. 그것 없이는 "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; 
     } 
    }