在JavaScript中如何实现求最大公共子串-tutorial js-php.cn

Rumah

hujung hadapan web

tutorial js

在JavaScript中如何实现求最大公共子串

Jun 08, 2018 am 10:37 AM

javascript

这篇文章主要介绍了JavaScript实现求最大公共子串的方法,涉及javascript针对字符串的遍历、匹配、运算等相关操作技巧,需要的朋友可以参考下

本文实例讲述了JavaScript实现求最大公共子串的方法。分享给大家供大家参考，具体如下：

求最大公共子串，常见的做法是使用矩阵。假设有字符串：abcdefg和字符串abcd，则可构成如下表所示矩阵。

可以，需要改变一下策略，如果该项匹配，则该项的值为再设为1，而是其对角线a[i-1, j-1](i > 1 && j > 1)的值+1，这样便可以只使用一个一维数组。对两个字符串的每一项都进行比较，若匹配则该项为1，不匹配则为0。然后求出对角线最长为1的那一段序列，即为最大公共子串。看上面的分开，似乎得使用二维数组了，在两个字符串都较大的情况下不是很划算，是否可以进一步优化？

以一个字符串作为“行”，另一个作为“列”，比较两个字符串各项的值，用另外一个变量记录数组的最大值和字符串的起始位置。代码如下：

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

Salin selepas log masuk

但代码其实并不是最优的，为什么？因为上面的写法必须等待两层循环都完成。有没有相对更快一些的方法呢？

设有字符串a、b，其长度分别为len1、len2，其公共字子串一定是 <= 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;;
}

Salin selepas log masuk

先比较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;

Salin selepas log masuk

上面是我整理给大家的，希望今后会对大家有帮助。

在vue.js中使用Nginx来解决跨域

在vue+webpack中如何实现异步组件加载？

Atas ialah kandungan terperinci 在JavaScript中如何实现求最大公共子串. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!

Kenyataan Laman Web ini

Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn