增量包算法，时间复杂度n+2m

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了增量包算法，时间复杂度n+2m，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2110字，纯文字阅读大概需要4分钟。

内容图文

 

研究了编辑距离、lcd等字符比较的算法，发现它们的时间复杂度和空间复杂度都在n*m，太复杂了。脑海想了下人是怎么比较字符的，联想出动态规划公式，之后就有了这个字符扫描比较法。

设字符s1长度为n,字符s2长度为m，

当s1[n1]!==s2[n2], 扫描s2求出d1,l1,扫描s1求出d2,l2, 比较l1、l2、d1、d2，移动n1、n2,重复这个过程

// 动态公式
// d1==0
// n1=n1+l1 l1>l2 或者 l1==l2 d1<d2
// n2=n2+d1+l1 l1>l2
//
// n1=n1+d2+l2 l1<l2 或者 l1==l2 d1>d2
// n2=n2+l2 l1<l2

//定义两个字符
var s1="afbrcd",s2="aftcdad";

//扫描法，复杂度为 n+m
//生产增量包
function makeChunk(s1,s2) {
  var n=s1.length,m=s2.length;//长度
  var n1=0,n2=0;//扫描点
  const chunkArr=[]
//开始扫描
  while (n1<n&&n2<m){
    let nn1=n1;
    let nn2=n2;
    if(s1[nn1]===s2[nn2]){
      nn1++;
      nn2++;
      while (nn1<n&&nn2<m&&s1[nn1]===s2[nn2]){
        nn1++;
        nn2++;
      }
      chunkArr.push(['e',n1,nn1-n1,n2,nn2])
      n1=nn1;
      n2=nn2;
    }else{
      //求n1,n2,d1,d2,l1,l2
      nn1=n1;
      nn2++;
      while (nn2<m&&s1[n1]!==s2[nn2]){
        nn2++;
      }
      let d1=nn2-n2;
      let l1=0;
      while (nn1<n&&nn2<m&&s1[nn1]===s2[nn2]){
        nn1++;
        nn2++;
        l1++;
      }
      nn2=n2;
      nn1++;
      while (nn1<n&&s1[nn1]!==s2[n2]){
        nn1++;
      }
      let d2=nn1-n1;
      let l2=0;
      while (nn1<n&&nn2<m&&s1[nn1]===s2[nn2]){
        nn1++;
        nn2++;
        l2++;
      }
      //结束
      if(l1>l2){
        chunkArr.push(['a',s2.substr(n2,d1),n1,n2,d1])
        chunkArr.push(['e',n1,l1,n2+d1,l1])
        n1=n1+l1;
        n2=n2+d1+l1;
      }else if(l1<l2){
        // chunkArr.push(['d',n1,d2,s1.substr(n1,d2)])
        chunkArr.push(['e',n1+d2,l2,n2,l2])
        n1=n1+d2+l2;
        n2=n2+l2;
      }else{
        if(d1<d2&&l1>0){
          chunkArr.push(['a',s2.substr(n2,d1),n1,n2,d1])
          n2=n2+d1;
        }else if(d1>d2&&l1>0){
          // chunkArr.push(['d',n1,d2,s1.substr(n1,d2)])
          n1=n1+d2;
        }else{
          var lastC=chunkArr[chunkArr.length-1]
          if(lastC[0]==='r'){
            lastC[4]=lastC[4]+1;
            lastC[1]=s2.substr(lastC[3],lastC[4])
          }else{
            chunkArr.push(['r',s2.substr(n2,1),n1,n2,1])
          }
          n1=n1+1;
          n2=n2+1;
        }
      }

    }
  }
  if(n1<n){
    // chunkArr.push(['d',n1,n-n1,s1.substr(n1,n-n1)])
  }
  if(n2<m){
    chunkArr.push(['a',s2.substr(n2,m-n2),n1,n2,m-n2])
  }
  return chunkArr;
}

//执行增量包
function execChunk(s1,chunk){
  var ns=''
  for(let i=0;i<chunk.length;i++){
    const arr=chunk[i];
    if(arr[0]==='e'){
      ns=ns+s1.substr(arr[1],arr[2])
    }else if(arr[0]==='r'){
      ns=ns+arr[1]
    }else if(arr[0]==='a'){
      ns=ns+arr[1]
    }
  }
  return ns
}


const chunk=makeChunk(s1,s2);
console.log(chunk)
const nstr=execChunk(s1,chunk)
console.log(nstr,nstr===s2)

 

内容总结

以上是互联网集市为您收集整理的增量包算法，时间复杂度n+2m全部内容，希望文章能够帮你解决增量包算法，时间复杂度n+2m所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---