研究了编辑距离、lcd等字符比较的算法，发现它们的时间复杂度和空间复杂度都在n*m，太复杂了。脑海想了下人是怎么比较字符的，联想出动态规划公式，之后就有了这个字符扫描比较法。
设字符s1长度为n,字符s2长度为m，
当s1[n1]!==s2[n2], 扫描s2求出d1,l1,扫描s1求出d2,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
//扫描法，复杂度为 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 if(n1+1<n&&n2+1<m&&s1[n1+1]===s2[n2+1]){
chunkArr.push(['r',s2.substr(n2,1),n1,n2,1]);
n1=n1+1;
n2=n2+1;
}else{
//求n1,n2,d1,d2,l1,l2
nn1=n1;
nn2=n2+1;
while (nn2<m&&s1[n1]!==s2[nn2]){
nn2++;
}
let d1=nn2-n2;
nn1=n1+1;
nn2=n2;
while (nn1<n&&s1[nn1]!==s2[n2]){
nn1++;
}
let d2=nn1-n1;
//结束
if(d1<d2){
chunkArr.push(['r',s2.substr(n2,1),n1,n2,1])
// n1=n1+1;
n2=n2+1;
}else if(d1>d2){
// chunkArr.push(['d',n1,1,s1.substr(n1,1)])
n1=n1+1;
// n2=n2+1;
}else{
chunkArr.push(['r',s2.substr(n2,1),n1,n2,1])
n1=n1+1;
n2=n2+1;
}
}
}
//压缩指令
for(let i=0;i<chunkArr.length;i++){
const arr=chunkArr[i];
if(arr[0]==='r'){
chunkArr[i]=[arr[0],arr[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
}
//定义两个字符
var s1=""191010",UrlNode:d.b.UrlNode}},methods:{rpush:function(){w.a.push({path:Object(h.a)("wlh_intro"),query:d.b.query})},forward1:function(){l.a.forward({data:{url:"index.html"}})},forward2:function(){l.a.forward({data:{url:"login.html",redirectURL:"index.html"}})},forward3:function(){l.a.forward({data:{url:",
s2=""1910011",UrlNode:d.b.UrlNode}},methods:{rpush:function(){w.a.push({path:Object(h.a)("wlh_intro"),query:d.b.query})},forward1:function(){l.a.forward({data:{url:"index.html"}})},forward2:function(){l.a.forward({data:{url:"login.html",redirectURL:"index.html"}})},forward3:function(){l.a.forward({data:{url:";
const chunk=makeChunk(s1,s2);
console.log(chunk)
const nstr=execChunk(s1,chunk)
console.log(nstr===s2)
console.log(nstr===s2)
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<title>增量包算法</title>
</head>
<style>
.container{
1000px;
margin: 0 auto;
}
.item{
margin-bottom: 20px;
vertical-align: middle;
float: none;
clear: both;
}
.item label{
100px;
float: left;
}
.item textarea{
60%;
min-height: 100px;
}
</style>
<script>
//扫描法，复杂度为 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])
n1=nn1;
n2=nn2;
}else if(n1+1<n&&n2+1<m&&s1[n1+1]===s2[n2+1]){
chunkArr.push(['r',s2.substr(n2,1),n1,n2,1]);
n1=n1+1;
n2=n2+1;
}else{
//求d1,d2
nn1=n1;
nn2=n2+1;
while (nn2<m&&s1[n1]!==s2[nn2]){
nn2++;
}
let d1=nn2-n2;
nn1=n1+1;
nn2=n2;
while (nn1<n&&s1[nn1]!==s2[n2]){
nn1++;
}
let d2=nn1-n1;
//结束
if(d1<d2){
chunkArr.push(['a',s2.substr(n2,1)])
// n1=n1+1;
n2=n2+1;
}else if(d1>d2){
// chunkArr.push(['d',n1,1,s1.substr(n1,1)])
n1=n1+1;
// n2=n2+1;
}else{
chunkArr.push(['r',s2.substr(n2,1),n1,n2,1])
n1=n1+1;
n2=n2+1;
}
}
}
if(n2<m){
chunkArr.push(['a',s2.substr(n2,m-n2)])
}
//压缩指令
const minChunk=[]
for(let i=0;i<chunkArr.length;i++){
let arr=chunkArr[i];
if(arr[0]==='e'&&arr[2]<String(arr[1]).length+8){
arr=['a',s1.substr(arr[1],arr[2])]
}
if(arr[0]==='r'){
arr=['a',arr[1]]
}
var lastArr=minChunk[minChunk.length-1];
if(arr[0]==='a'&&lastArr&&lastArr[0]==='a'){
lastArr[1]=lastArr[1]+arr[1];
}else{
minChunk.push(arr)
}
}
return minChunk;
}
//执行增量包
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]==='a'){
ns=ns+arr[1]
}
}
return ns
}
</script>
<script>
function s1makeChunk() {
var s1=document.getElementById('s1').value;
var s2=document.getElementById('s2').value;
var chunk=makeChunk(s1,s2)
var cstr=JSON.stringify(chunk)
document.getElementById('chunk').value=cstr
return cstr
}
function s1execChunk() {
var s1=document.getElementById('s1').value;
var s2=document.getElementById('s2').value;
var cstr=document.getElementById('chunk').value
if(!cstr){
cstr=s1makeChunk();
}
var chunk=JSON.parse(cstr)
var ns=execChunk(s1,chunk)
document.getElementById('result').innerText='结果为'+(ns===s2);
document.getElementById('ns').value=ns;
}
</script>
<body>
<div class="container">
<div class="item">
增量包算法:时间复杂度 2*n ~ 2*n阶和 之间
</div>
<div class="item">
<label>输入字符s1：</label> <textarea id="s1">ill:"071b136b",test:"acf98235",wlh_audit_ok:"0cfbdb93",wl</textarea>
</div>
<div class="item">
<label>输入字符s2：</label> <textarea id='s2'>ill:"acf98235",test:"0cfbdb93",wlh_audit_ok:"0cfbdb93",wl</textarea>
</div>
<div class="item">
<label>s1-->s2：</label> <textarea id='chunk'></textarea><button onClick="s1makeChunk()">生产增量包：</button>
</div>
<div class="item">
<label>结果：</label> <textarea id="ns"></textarea><button onClick="s1execChunk()">执行增量包：</button>
</div>
<div id="result"></div>
</div>
</body>
</html>