用后缀数组，求两个字符的公共子串,或者两个文件的公共子串

复杂度

1、求后缀数组，用的二分查找法和基类比较，所以时间复杂度是 n*lg2n，只保存后缀的位置，空间复杂度是n

2、比较查找，没有公共部分的情况，str1排名的最小值>str2排名的最大值 或者 str1排名的最大值>str2排名的最小值，就认为没有公共部分，复杂度为2

3、比较查找，有公共部分的情况，按照n、m从小到大的顺序查找的，复杂度为n+m

所以：

时间复杂度是 O(2n*logn)和O(2n*logn+2n)之间，logn的底数是2

空间复杂度是O(2n)

什么是后缀数组

1、给字符的后缀排好序的数组

2、保持的值是字符的后缀

3、排序规则是基类排序，从小到大

后缀

后缀就是从字符串的某个位置i到字符串末尾的子串，我们定义以s的第i个字符为第一个元素的后缀为suff(i)

 

例如

字符 s='123456',它的后缀数组表示为[ 0, 1, 2, 3, 4, 5 ]，也即是 [123456，23456，3456，456，56，6]

字符 s='热点112',它的后缀数组表示为[ 2, 3, 4, 1, 0 ]，也即是[112，12，2，点112，热点112]

 

算法思路

1、对字符str1进行排序，求出后缀数组sa1,对字符str2进行排序，求出后缀数组sa2

2、设 n表示字符str1的排名，m表示字符str2的排名，初始设 n=0，m=0

sa1[n]表示排名为n的字符str1位置

sa2[m]表示排名为m的字符str2位置

逻辑部分

初次查询从n=m=0开始，从小到大比较位置sa1[i]和sa2[j]，如果字符相同，则求出相同部分的长度len，更新查询起始位置 n=i,m=j

下次查询，从n、m位置从小到大继续比较位置sa1[i]和sa2[j]，如果字符相同，则求出相同部分的长度len，更新查询起始位置 n=i,m=j

如果 n<sa1.length&&m<sa2.length，重复上述过程

3、此时按照排名顺序求出了所有的公共部分，还需要去重

因为后一个字符长度，必然比前一个字符长度小，所以判断当前和上一个有没有重叠，重叠的话就去掉当前，保留了最长的公共子串

4、返回的数据格式如下,按照str1位置顺序排列的

[

[str1位置i、长度len、str2位置j],

[str1位置i、长度len、str2位置j]

]

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

    return sa
}


//用后缀数组，求两个字符的公共子串,也就是两个文件的公共部分
function getHotCommon(str1,str2) {
    var sa1=getSa(str1);//后缀数组，排序
    var sa2=getSa(str2);//后缀数组，排序

    //再次排序,获取合并后的后缀数组
    var arr=[]
    var n1=0,n2=0;
    while (n1<sa1.length&&n2<sa2.length) {
        var d=compare(sa1[n1],sa2[n2],str1,str2);
        if(d===1){
            arr.push([1,sa2[n2]])
            n2++;
        }else if(d===-1){
            arr.push([0,sa1[n1]])
            n1++
        }else{
            arr.push([0,sa1[n1]])
            arr.push([1,sa2[n2]])
            n1++;
            n2++;
        }
        if(n1===sa1.length){
            arr.push([1,sa2[n2]])
        }else if(n2===sa2.length){
            arr.push([0,sa1[n1]])
        }
    }
    //求height数组，获取公共子序列
    var common=[]
    for(var i=0;i<arr.length-1;i++){
        var cur=arr[i]
        var next=arr[i+1]
        if(cur[0]!==next[0]){
            var n
            var m
            if(cur[0]===0){
                n=cur[1]
                m=next[1]
            }else{
                n=next[1]
                m=cur[1]
            }
            var len=0;
            while(n+len<str1.length&&m+len<str2.length&&str1[n+len]===str2[m+len]){
                len++;
            }
            if(len>0){
                common.push([n,m,len]);
            }
        }
    }
    //排序
    common.sort(function (arr1,arr2) {
        return arr1[0]-arr2[0]
    })
    //去掉相交的部分
    var narr1=[]
    for(var i=0;i<common.length;i++){
        if(narr1.length===0){
            narr1.push(common[i])
        }else{
            var last=narr1[narr1.length-1];
            var cur=common[i]
            if(last[0]+last[2]>cur[0]){
                if(cur[2]>last[2]){
                    last[2]=cur[0]-last[0]
                    if(last[2]>0){
                        narr1.push(cur)
                    }else{
                        last[0]=cur[0]
                        last[1]=cur[1]
                        last[2]=cur[2]
                    }
                }
            }else{
                narr1.push(cur)
            }
        }
    }
//排序
    narr1.sort(function (arr1,arr2) {
        return arr1[1]-arr2[1]
    })
    var narr=[]
    for(var i=0;i<narr1.length;i++){
        if(narr.length===0){
            narr.push(narr1[i])
        }else{
            var last=narr[narr.length-1];
            var cur=narr1[i]
            if(last[2]+last[1]>cur[1]){
                if(cur[2]>last[2]){
                    last[2]=cur[1]-last[1]
                    if(last[2]>0){
                        narr.push(cur)
                    }else{
                        last[0]=cur[0]
                        last[1]=cur[1]
                        last[2]=cur[2]
                    }
                }
            }else{
                narr.push(cur)
            }
        }
    }
    return narr;
}

//demo
const str1='211234567123';
const str2='4123456711';
//获取公共子串的位置和长度，arr[字符1的位置、长度、字符2的位置]
const narr=getHotCommon(str1,str2);
console.log(narr)
//字符1的公共子串的位置和长度
const str1Arr=narr.map(function (arr) {
    return str1.substr(arr[0],arr[2])
})
//字符2的公共子串的位置和长度
const str2Arr=narr.map(function (arr) {
    return str2.substr(arr[1],arr[2])
})
//相同输出
console.log(str1Arr)//=>[ '12345671', '1' ]
console.log(str2Arr)//=>[ '12345671', '1' ]

 getLongCommon.html

<!DOCTYPE html>
<html>
<head>
    <meta charset="utf-8" />
    <title>后缀数组求公共部分</title>
</head>
<script>
    //查找
    function find(str,hasSortArr,callback) {
        var l=0,r=hasSortArr.length;
        var index=-1;
        if(hasSortArr.length>0){
            var 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;
            }
            var 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){
                var m=(l+r)>>1;
                //比较下坐标大小
                var 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]
    }
    //比较函数
    var compare=function (n1,n2,str1,str2) {
        var dis=0;
        var len=0;
        while (dis===0&&n1+len<=str1.length&&n2+len<=str2.length){
            //超过字符，返回小于
            if(n1+len===str1.length){
                dis=-1
            }else if(n2+len===str2.length){
                dis=1
            }else if(str1.charCodeAt(n1+len)>str2.charCodeAt(n2+len)){
                dis=1;
            }else if(str1.charCodeAt(n1+len)<str2.charCodeAt(n2+len)){
                dis=-1;
            }else{
                len++;
            }
        }
        return dis;
    };
    //SA[i]表示排名为i的后缀下标、rk[i]表示起始位置的下标为i的后缀的排名
    function getSa(str) {
        var sLen=str.length;//总共排名长度
        //后缀数组
        var sa=[];
        for(var i=0;i<sLen;i++){
            var [n,index]=find(i,sa,function (n1,n2) {
                return compare(n1,n2,str,str)
            })
            sa.splice(n,0,i)
        }

        return sa
    }


    //用后缀数组，求两个字符的公共子串,也就是两个文件的公共部分
    function getHotCommon(str1,str2) {
        var sa1=getSa(str1);//后缀数组，排序
        var sa2=getSa(str2);//后缀数组，排序

        //再次排序,获取合并后的后缀数组
        var arr=[]
        var n1=0,n2=0;
        while (n1<sa1.length&&n2<sa2.length) {
            var d=compare(sa1[n1],sa2[n2],str1,str2);
            if(d===1){
                arr.push([1,sa2[n2]])
                n2++;
            }else if(d===-1){
                arr.push([0,sa1[n1]])
                n1++
            }else{
                arr.push([0,sa1[n1]])
                arr.push([1,sa2[n2]])
                n1++;
                n2++;
            }
            if(n1===sa1.length){
                arr.push([1,sa2[n2]])
            }else if(n2===sa2.length){
                arr.push([0,sa1[n1]])
            }
        }
        //求height数组，获取公共子序列
        var common=[]
        for(var i=0;i<arr.length-1;i++){
            var cur=arr[i]
            var next=arr[i+1]
            if(cur[0]!==next[0]){
                var n
                var m
                if(cur[0]===0){
                    n=cur[1]
                    m=next[1]
                }else{
                    n=next[1]
                    m=cur[1]
                }
                var len=0;
                while(n+len<str1.length&&m+len<str2.length&&str1[n+len]===str2[m+len]){
                    len++;
                }
                if(len>0){
                    common.push([n,m,len]);
                }
            }
        }
        //排序
        common.sort(function (arr1,arr2) {
            return arr1[0]-arr2[0]
        })
        //去掉相交的部分
        var narr1=[]
        for(var i=0;i<common.length;i++){
            if(narr1.length===0){
                narr1.push(common[i])
            }else{
                var last=narr1[narr1.length-1];
                var cur=common[i]
                if(last[0]+last[2]>cur[0]){
                    if(cur[2]>last[2]){
                        last[2]=cur[0]-last[0]
                        if(last[2]>0){
                            narr1.push(cur)
                        }else{
                            last[0]=cur[0]
                            last[1]=cur[1]
                            last[2]=cur[2]
                        }
                    }
                }else{
                    narr1.push(cur)
                }
            }
        }
//排序
        narr1.sort(function (arr1,arr2) {
            return arr1[1]-arr2[1]
        })
        var narr=[]
        for(var i=0;i<narr1.length;i++){
            if(narr.length===0){
                narr.push(narr1[i])
            }else{
                var last=narr[narr.length-1];
                var cur=narr1[i]
                if(last[2]+last[1]>cur[1]){
                    if(cur[2]>last[2]){
                        last[2]=cur[1]-last[1]
                        if(last[2]>0){
                            narr.push(cur)
                        }else{
                            last[0]=cur[0]
                            last[1]=cur[1]
                            last[2]=cur[2]
                        }
                    }
                }else{
                    narr.push(cur)
                }
            }
        }
        return narr;
    }
</script>
<style>
    .container{
        width: 1000px;
        margin: 0 auto;
    }
    .item{
        margin-bottom: 20px;
        vertical-align: middle;
        float: none;
        clear: both;
    }
    .item label{
        width: 100px;
        float: left;
    }
    .item textarea{
        width: 60%;
        min-height: 100px;
    }
</style>
<body>

<div class="container">
    <div class="item">
        后缀数组求公共部分:时间复杂度 2*nlog2N
    </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：</label> <textarea id='chunk'></textarea>
    </div>
    <div class="item">
        <label>s2：</label> <textarea id="chunk2"></textarea>
    </div>
    <div class="item">
        <label>common：</label> <textarea id='common'></textarea>
        <button onClick="s1execChunk()">执行common：</button>
    </div>
    <div id="result"></div>
</div>

</body>
<script>
    function s1execChunk() {
        var str1=document.getElementById('s1').value;
        var str2=document.getElementById('s2').value;
        //获取公共子串的位置和长度，arr[字符1的位置、长度、字符2的位置]
        var narr=getHotCommon(str1,str2);
        console.log(narr)
//字符1的公共子串的位置和长度
        var arr1=[]
        var str1Arr=narr.map(function (arr) {
            arr1.push([arr[0],arr[2]])
            return str1.substr(arr[0],arr[2])
        })
//字符2的公共子串的位置和长度
        var arr2=[]
        var str2Arr=narr.map(function (arr) {
            arr2.push([arr[1],arr[2]])
            return str2.substr(arr[1],arr[2])
        })
        document.getElementById('chunk').innerText=JSON.stringify(arr1);
        document.getElementById('chunk2').innerText=JSON.stringify(arr2);

        document.getElementById('common').innerText=str2Arr.join('');
        document.getElementById('result').innerText='结果为'+(str1Arr.join('')===str2Arr.join(''));
    }
</script>

</html>