JavaScript에서 가장 큰 공통 부분 문자열을 찾는 방법-JS 튜토리얼-php.cn

집

웹 프론트엔드

JS 튜토리얼

JavaScript에서 가장 큰 공통 부분 문자열을 찾는 방법

Jun 08, 2018 am 10:37 AM

javascript

이 글에서는 주로 자바스크립트의 문자열 순회, 일치, 연산 및 기타 관련 연산 기술을 포함하여 자바스크립트에서 최대 공통 부분 문자열을 구현하는 방법을 소개합니다. 도움이 필요한 친구들은 참고할 수 있습니다

이 글의 예는 JavaScript 하위 문자열 메서드의 최대 공통 하위 문자열입니다. 참고를 위해 모든 사람과 공유하세요. 세부 사항은 다음과 같습니다.

가장 큰 공통 부분 문자열을 찾으려면 일반적인 방법은 행렬을 사용하는 것입니다. 문자열 abcdefg와 문자열 abcd가 있다고 가정하면 다음 표와 같은 행렬이 구성될 수 있습니다.

예, 전략을 변경해야 합니다. 항목이 일치하면 항목의 값이 다시 1로 설정되지만 대각선은 a[i-1, j-1](i > 1 && j > The ; 1)의 값은 +1이므로 1차원 배열만 사용할 수 있습니다. 두 문자열의 각 항목을 비교하여 일치하면 1, 일치하지 않으면 0이 됩니다. 그런 다음 가장 큰 공통 부분 문자열인 가장 긴 대각선이 1인 시퀀스를 찾습니다. 위의 분리를 보면 2차원 배열을 사용해야 할 것 같은데, 두 문자열이 모두 큰 경우에는 비용 효율성이 별로 높지 않습니다.

한 문자열을 "행"으로, 다른 문자열을 "열"로 사용하여 두 문자열의 각 항목 값을 비교하고 다른 변수를 사용하여 배열의 최대값과 시작 위치를 기록합니다. 끈. 코드는 다음과 같습니다.

function LCS(str1, str2) {
 if (str1 === &quot;&quot; || str2 === &quot;&quot;) {
  return &quot;&quot;;
 }
 var len1 = str1.length;
 var len2 = str2.length;
 var a = new Array(len1);
 var maxLen = 0;
 var maxPos = 0;
 for (var i = 0; i &lt; len1; i++) { //行
  for (var j = len2 - 1; j &gt;= 0; j--) {//列
   if (str1.charAt(j) == str2.charAt(i)) {
    if (i === 0 || j === 0) {
     a[j] = 1;
    } else {
     a[j] = a[j - 1] + 1;
    }
   } else {
    a[j] = 0;
   }
   if (a[j] &gt; maxLen) {
    maxLen = a[j];
    maxPos = j;
   }
  }
 }
 return str1.substr(maxPos - maxLen + 1, maxLen);
}

로그인 후 복사

그런데 코드가 실제로 최적이 아닌 이유는 무엇입니까? 위의 작성 방법은 두 루프 레이어가 모두 완료될 때까지 기다려야 하기 때문입니다. 상대적으로 더 빠른 방법이 있습니까?

길이가 각각 len1과 len2인 문자열 a와 b가 있다고 가정합니다. 해당 문자열의 공통 부분 문자열은 <= Math.min(len1, len2)이어야 하고 부분 문자열은 연속적이어야 하며 a와 b에 속해야 합니다.

function findMaxSubStr(s1,s2){
 var str= &quot;&quot;,
  L1=s1.length,
  L2=s2.length;
 if (L1&gt;L2){
  var s3=s1;
  s1=s2;
  s2=s3;
  s3 = null;
  L1=s2.length;
  L2 = s1.length;
 }
 for (var i=L1; i &gt; 0; i--) {
  for (var j= 0; j &lt;= L2 - i &amp;&amp; j &lt; L1; j++){
   str = s1.substr(j, i);
   if (s2.indexOf(str) &gt;= 0) {
    return str;
   }
  }
 }
 return &quot;&quot;;
}

로그인 후 복사

먼저 s1과 s2의 길이를 비교한 다음 더 짧은 문자열을 선택하세요. substr(idex, len), 더 짧은 문자열을 가져와 해당 하위 문자열을 가져온 다음, 더 긴 문자열에 해당 문자열이 있는지 확인하고, 존재하면 직접 반환하고, 그렇지 않으면 다음 숫자를 삭제하세요.

완전한 예:

&lt;!DOCTYPE html PUBLIC &quot;-//W3C//DTD XHTML 1.0 Transitional//EN&quot; &quot;http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd&quot;&gt;
&lt;html xmlns=&quot;http://www.w3.org/1999/xhtml&quot;&gt;
 &lt;head&gt;
 &lt;title&gt;www.jb51.net&lt;/title&gt;
 &lt;style type=&#39;text/css&#39;&gt;
 body {background-color:#fff;}
 &lt;/style&gt;
 &lt;/head&gt;
 &lt;body&gt;
&lt;script type=&#39;text/javascript&#39;&gt;
function LCS(str1, str2) {
 if (str1 === &quot;&quot; || str2 === &quot;&quot;) {
 return &quot;&quot;;
 }
 var len1 = str1.length;
 var len2 = str2.length;
 var a = new Array(len1);
 var maxLen = 0;
 var maxPos = 0;
 for (var i = 0; i &lt; len1; i++) { //行
 for (var j = len2 - 1; j &gt;= 0; j--) {//列
 if (str1.charAt(j) == str2.charAt(i)) {
 if (i === 0 || j === 0) {
  a[j] = 1;
 } else {
  a[j] = a[j - 1] + 1;
 }
 } else {
 a[j] = 0;
 }
 if (a[j] &gt; maxLen) {
 maxLen = a[j];
 maxPos = j;
 }
 }
 }
 return str1.substr(maxPos - maxLen + 1, maxLen);
}
function findMaxSubStr(s1,s2){
 var str= &quot;&quot;,
 L1=s1.length,
 L2=s2.length;
 if (L1&gt;L2) {
 var s3=s1;
 s1=s2;
 s2=s3;
 s3 = null;
 L1=s2.length;
 L2 = s1.length;
 }
 for (var i=L1; i &gt; 0; i--) {
 for (var j= 0; j &lt;= L2 - i &amp;&amp; j &lt; L1; j++){
   str = s1.substr(j, i);
   if (s2.indexOf(str) &gt;= 0) {
 return str;
  }
  }
 }
 return &quot;&quot;;
}
 !(function() {
 var tmpArr = [];
 for (var i = 97; i &lt; 97 + 26; i++) {
 tmpArr.push(String.fromCharCode(i));
 }
 var s2 = tmpArr.join(&quot;&quot;);
 tmpArr.sort(function() {return Math.random() &gt; 0.7;});
 var s1 = new Array(600).join(tmpArr.join(&quot;&quot;));
 var date = getNow();
 alert( &quot;消耗时间：&quot; + (getNow() - date) + &quot;秒 &quot; + LCS(s1, s2));
 date = getNow();
 alert( &quot;消耗时间：&quot; + (getNow() - date) + &quot;秒 &quot; + findMaxSubStr(s1, s2) );
 })();
function getNow() {
 return new Date().getTime();
}
&lt;/script&gt;
 &lt;/body&gt;
&lt;/html&gt;

로그인 후 복사

위 내용은 제가 모든 사람을 위해 정리한 내용입니다. 앞으로 모든 사람에게 도움이 되기를 바랍니다.