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

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

亚连

풀어 주다： 2018-06-08 10:37:02

원래의

2272명이 탐색했습니다.

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

이 글의 예는 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 === "" || str2 === "") {
  return "";
 }
 var len1 = str1.length;
 var len2 = str2.length;
 var a = new Array(len1);
 var maxLen = 0;
 var maxPos = 0;
 for (var i = 0; i < len1; i++) { //行
  for (var j = len2 - 1; j >= 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] > 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= "",
  L1=s1.length,
  L2=s2.length;
 if (L1>L2){
  var s3=s1;
  s1=s2;
  s2=s3;
  s3 = null;
  L1=s2.length;
  L2 = s1.length;
 }
 for (var i=L1; i > 0; i--) {
  for (var j= 0; j <= L2 - i && j < L1; j++){
   str = s1.substr(j, i);
   if (s2.indexOf(str) >= 0) {
    return str;
   }
  }
 }
 return "";
}

로그인 후 복사

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

완전한 예:

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

로그인 후 복사

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