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

JavaScript에서 가장 큰 공통 부분 문자열을 찾는 방법에 대한 자세한 설명

小云云

풀어 주다： 2018-02-05 09:44:03

원래의

1823명이 탐색했습니다.

이 글은 자바스크립트의 순회, 매칭, 연산, 기타 관련 연산 기술이 포함된 자바스크립트에서 가장 큰 공통 부분 문자열을 찾는 방법을 주로 소개합니다. 필요한 친구들이 참고하면 도움이 될 것입니다.

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

00001 비교 항목이 1인 경우 일치하고, 일치하지 않으면 0입니다. 그런 다음 가장 큰 공통 부분 문자열인 가장 긴 대각선이 1인 시퀀스를 찾습니다. 위의 분리를 보면 2차원 배열을 사용해야 할 것 같은데, 두 문자열이 모두 큰 경우에는 비용 효율성이 별로 높지 않습니다. 예, 전략을 변경해야 합니다. 항목이 일치하면 항목의 값이 다시 1로 설정되지만 대각선은 이므로 1차원 배열만 사용할 수 있습니다. 한 문자열을 "행"으로 다른 문자열을 "열"로 사용하여 두 문자열의 각 항목 값을 비교하고 다른 변수를 사용하여 배열의 최대값과 시작 위치를 기록합니다. 끈. 코드는 다음과 같습니다.

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

로그인 후 복사

먼저 s1과 s2의 길이를 비교한 다음 더 짧은 문자열을 선택하세요.

<!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>

로그인 후 복사

관련 권장 사항:

0	0	0	b	0	1	0
0	0	0	c	0	0	1
0	0	0	d	0	0	0
0	0	0			a[i-1, j-1](i > 1 && j > The ; 1)의 값은 +1
	그런데 코드가 실제로 최적이 아닌 이유는 무엇입니까? 위의 작성 방법은 두 루프 레이어가 모두 완료될 때까지 기다려야 하기 때문입니다. 상대적으로 더 빠른 방법이 있습니까?	길이가 각각 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 ""; } 로그인 후 복사	, 더 짧은 문자열을 가져와 해당 하위 문자열을 가져온 다음, 더 긴 문자열에 해당 문자열이 있는지 확인하고, 존재하면 직접 반환하고, 그렇지 않으면 다음 숫자를 삭제하세요.	전체 예: