求字符1和字符2不重复的公共子串,也就是热点关键字

//查找
function find(str,hasSortArr,callback) {
    let l=0,r=hasSortArr.length;
    let index=-1;
    if(hasSortArr.length>0){
        const ri=callback(str,hasSortArr[r-1]);
        if(ri===1){
            return [r,-1]
        }else if(ri===0){
            return [r-1,r-1]
        }else{
            r=r-1;
        }
        const li=callback(str,hasSortArr[0]);
        if(li===-1){
            return [0,-1]
        }else if(li===0){
            return [0,0]
        }else{
            l=l+1;
        }
        while(r-l>0){
            const m=(l+r)>>1;
            //比较下坐标大小
            const order=callback(str,hasSortArr[m])
            if(order===1){
                l=Math.max(l+1,m)
            }else if(order===-1){
                r=Math.min(r-1,m)
            }else{
                l=r=m;
                index=m;
            }
        }
    }
    return [(l+r)>>1,index]
}
//SA[i]表示排名为i的后缀下标、rk[i]表示起始位置的下标为i的后缀的排名
function getSa(str) {
    const sLen=str.length;//总共排名长度
    //排名函数
    const compare=function (n1,n2) {
        let dis=0;
        let len=0;
        while (dis===0){
            //超过字符，返回小于
            if(n1+len===sLen){
                dis=-1
            }else if(str[n1+len]>str[n2+len]){
                dis=1;
            }else if(str[n1+len]<str[n2+len]){
                dis=-1;
            }else{
                len++;
            }
        }
        return dis;
    };
    //后缀数组
    const sa=[];
    for(let i=0;i<sLen;i++){
        const [n,index]=find(i,sa,compare)
        sa.splice(n,0,i)
    }

    return sa
}


//求字符1和字符2不重复的公共子串,求热点关键字
function getHotCommon(str1,str2) {
    const sa1=getSa(str1);
    console.log(sa1)
    const common=[]
    for(let i=0;i<str2.length;i++){
        const [n,index]=find(i,sa1,function (n2,n1) {
            let dis=2;
            let len=0;
            while (dis===2){
                //超过字符，返回小于
                if(n1+len===str1.length&&n2+len===str2.length){
                    dis=0
                }else if(n1+len===str1.length){
                    dis=1
                }else if(n2+len===str2.length){
                    dis=-1
                }else if(str2.charCodeAt(n2+len)>str1.charCodeAt(n1+len)){
                    dis=1;
                }else if(str2.charCodeAt(n2+len)<str1.charCodeAt(n1+len)){
                    dis=-1;
                }else{
                    len++;
                }
            }
            return dis;
        })
        if(index===-1){
            let len=0;
            let len2=0;
            let m=n-1;
            while(i+len<str2.length&&sa1[n]+len<str1.length&&str2[i+len]===str1[sa1[n]+len]){
                len++;
            }
            while(n>0&&i+len2<str2.length&&sa1[m]+len2<str1.length&&str2[i+len2]===str1[sa1[m]+len2]){
                len2++;
            }
            if(len>len2){
                m=n;
                len2=len;
            }
            if(len2>0){
                if(common.length>0){
                    const last=common[common.length-1];
                    //如果不相交
                    if(last[0]+last[1]-1<sa1[m]||last[0]>sa1[m]+len2-1){
                        common.push([sa1[m],len2])
                    }else{
                        if(len2>last[1]){
                            last[1]=sa1[m]-last[0]
                            if(last[1]>0){
                                common.push([sa1[m],len2])
                            }else{
                                last[0]=sa1[m]
                                last[1]=len2
                            }
                        }
                    }
                }else{
                    common.push([sa1[m],len2])
                }


            }
        }else{
            common.push([sa1[n],str2.length-i])
            break;
        }
    }

    return common.map(function (arr) {
        return str1.substr(arr[0],arr[1])
    })
}
//demo
const str1=‘1热点2热点12‘;
const str2=‘123热点1212热点3‘;
console.log(getHotCommon(str1,str2))//=>[ ‘热点12‘, ‘热点‘ ]