摘要：后綴數(shù)組是處理字符串的利器它本身涉及許多輔助概念基本概念子串表示字符串的某一小段如擁有，，等子串。后綴后綴是字符串從某個(gè)位置起到達(dá)末尾的一種特殊子串。代碼如下司徒正美算法算法是和在年發(fā)表的論文中描述的線性時(shí)間內(nèi)構(gòu)造后綴數(shù)組的算法。

后綴數(shù)組是處理字符串的利器, 它本身涉及許多輔助概念.

表示字符串的某一小段, 如awbcdewg擁有 awbc， awbcd， awbcde等子串。

后綴是字符串從某個(gè)位置起到達(dá)末尾的一種特殊子串。后綴可以等于自身，相等于從一個(gè)字符開(kāi)始. 假令我們?cè)O(shè)計(jì)一個(gè)取后綴的函數(shù), 它可以這樣實(shí)現(xiàn):

function suffix(str, i ){
    if(i >= 0 || i <= str.length-1){
       return str.slice(i)
    }
    throw "i越界了"
}

后綴必須包含最后一個(gè)字符.

字符串rubylouvre，它的后綴就包含rubylouvre、ubylouvre、bylouvre、 ylouvre、louvre、ouvre，uvre、vre、 re、 e 它們都必須包含最后一個(gè)字符e。

字符串默認(rèn)的比較算法, "aa" < "ab" 返回true而不是返回false就是依靠這個(gè)標(biāo)準(zhǔn)進(jìn)行.

首先從左到右, 各自取得第一個(gè)字符, "a"與"a", 如果相同, 則比較各自的第二個(gè)字符. 否則, 比較其charCode值. 如i 和 b比, i的charCode為105, b的charCode為98, b肯定比i小, 那么不用再比較.

如果其中之一是另一個(gè)的前綴，則短的那個(gè)排前面：aaa < aaab

后端數(shù)組就是某個(gè)字符串的所有后綴按照字典順序進(jìn)行排序后得到的位置數(shù)組. 如字符串ADCEFD, 當(dāng)i從0到5遞增時(shí),我們通過(guò)上面的suffix函數(shù)得到其所有 后綴.

按字典排序后

這個(gè)[0,2,5,1,3,4]就是字符串的后綴數(shù)組.

// by 司徒正美
var str = "ADCEFD", arr = []
function spawnSuffix(str, arr){
     if(str){
        arr.push(str)
        spawnSuffix(str.slice(1), arr)
     }
 }
spawnSuffix(str, arr)
console.log(arr)
//["ADCEFD", "DCEFD", "CEFD", "EFD", "FD", "D"]
// 對(duì)abadefg的所有后綴子串?dāng)?shù)組進(jìn)行加工
var sa = arr.map(function(str, i){
  return {el: str, index: i}
}).sort(function(a, b){
 return a.el > b.el
}).map(function(obj){
 return obj.index  //可以加1，也可以不加，看你的習(xí)慣
})
console.log(sa)// [0, 2, 5, 1, 3, 4]

上面我們通過(guò)非常樸素的方式,逐個(gè)取得它的所有后綴,然后通過(guò)語(yǔ)言本身的sort方法進(jìn)行字典排序.這個(gè)sort在不同的宿主環(huán)境中,內(nèi)部采取的排序算法都不一樣,就是一個(gè)黑箱.

整個(gè)過(guò)程大家可以參考羅穗騫的論文，但由于語(yǔ)言的差異，我看不 懂他在寫什么，直接對(duì)著它的那張圖搞出來(lái)了。

// by 司徒正美
function getSuffix(str) {
    var len = str.length, 
        max = str.charCodeAt(0), 
        min = max,
        xbuckets = [],
        sa = [],
        rank = [];
    // 將用戶傳入的字符串全部轉(zhuǎn)換為charCode值，并求出最大最小值
    for (let i = 0; i < len; i++) {
        let c = str.charCodeAt(i);
        rank[i] = c;
        max = Math.max(max, c);
        min = Math.min(min, c);
    }
    //我們要對(duì)rank進(jìn)行計(jì)數(shù)排序，但是它們太大，都是90－128左右，
    // 這樣我們要?jiǎng)?chuàng)建上百個(gè)桶
    //我們通過(guò)減去最小值，來(lái)縮小規(guī)模, 現(xiàn)在只需2－10個(gè)桶就夠了。

    //這些新得到的數(shù)字其實(shí)在原論文中構(gòu)成一個(gè)叫 x 的數(shù)組
    //但是我們并沒(méi)有這樣用，而是讓它作為rank對(duì)象數(shù)組的一個(gè)屬性
    rank.forEach(function(el, i){
        rank[i] = {x: el - min + 1 };
    });
  
    var hasDuplicate = true, k = 0;
    while(hasDuplicate){
        //重置數(shù)據(jù)
        hasDuplicate = false;
        xbuckets.length = 0;
        //k倍增，隔空拼湊y數(shù)組
        //y作為基數(shù)排序的第二個(gè)關(guān)鍵字
        var d = 1 << k; k ++;
        rank.forEach(function(el, i){
            el.y = rank[i+ d] ? rank[i+ d].x: 0;
        });
        //根據(jù)關(guān)鍵字x，進(jìn)行基數(shù)排序
        rank.forEach(function(el){
            var index = el.x;
            if(!xbuckets[index]){
                xbuckets[index] = [el];
            }else{
                xbuckets[index].push(el);
            }
        });
        //對(duì)每個(gè)桶內(nèi)xbucket根據(jù)y進(jìn)行排序
        var newIndex = 1, last = {};
        xbuckets.forEach(function(bucket){
            if(bucket){
                let cache = {};
                bucket.sort(function(a, b){
                    return a.y - b.y;
                }).forEach(function(el ){
                    //重寫x
                    if(el.y !== last.y){
                        el.x = newIndex++;
                        cache[el.y] = el.x;
                    }else{
                        hasDuplicate = true;
                        el.x = cache[el.y];
                    }
                    last = el;
                });
            }
        });
    }
    //rank是從1開(kāi)始的，因此這里面要減1
    rank = rank.map(function(el, i ){
        sa[el.x - 1] = i;
        return el.x;
    });
    console.log("rank數(shù)組", rank);
    console.log("后綴數(shù)組", sa);
    return sa;
}

var ret = getSuffix("aabaaaab"); 
//ret:  3, 4, 5, 0, 6, 1, 7, 2 
/*

但這依賴于原生的sort, 我們可以將sort改成計(jì)數(shù)排序。

// by 司徒正美
function getSuffix(str) {
    var len = str.length, 
        max = str.charCodeAt(0), 
        min = max,
        xbuckets = [],
        sa = [],
        rank = [];
    // 字符串轉(zhuǎn)charCode
    for (let i = 0; i < len; i++) {
        let c = str.charCodeAt(i);
        rank[i] = c;
        max = Math.max(max, c);
        min = Math.min(min, c);
    }
    //壓縮charCode值
    rank.forEach(function(el, i){
        rank[i] = {x: el - min + 1 };
    });
    var hasDuplicate = true, k = 0;
    while(hasDuplicate){
        //重置數(shù)據(jù)
        hasDuplicate = false;
        xbuckets.length = 0;
        //倍增，目的是求關(guān)鍵字y
        var d = 1 << k; k ++;

        rank.forEach(function(el, i){
            //根據(jù)關(guān)鍵字x，進(jìn)行基數(shù)排序，并同時(shí)計(jì)算關(guān)鍵字y
            el.y = rank[i+ d] ? rank[i+ d].x: 0;
           
            var index = el.x;
            if(!xbuckets[index]){
                xbuckets[index] = [el];
            }else{
                xbuckets[index].push(el);
            }
        });

        var newIndex = 1, last = {};
        xbuckets.forEach(function(bucket){
            if(bucket){
                //使用計(jì)數(shù)排序?qū)γ總€(gè)桶再進(jìn)行排序
                var cache = {};
                var yxbuckets = [];
                bucket.forEach(function(el){
                    var index = el.y;
                    if(!yxbuckets[index]){
                        yxbuckets[index] = [el];
                    }else{
                        yxbuckets[index].push(el);
                    }
                });
                var j = 0;
                yxbuckets.forEach(function(ybucket){
                    if(ybucket){
                        ybucket.forEach(function(el){
                            if(el.y !== last.y){
                                el.x = newIndex++;
                                cache[el.y] = el.x;
                            }else{
                                hasDuplicate = true;
                                el.x = cache[el.y];
                            }
                            bucket[j++] = el; //這里可以不要
                            last = el;
                        });
                    }
                });
            }
        });
     
    }
    //rank是從1開(kāi)始的，因此這里面要減1
    rank = rank.map(function(el, i ){
        sa[el.x - 1] = i;
        return el.x;
    });
    console.log("rank數(shù)組", rank);
    console.log("后綴數(shù)組", sa);
    return sa;
}
var a = getSuffix("aabaaaab"); 

那么如何計(jì)算height？我們定義h[i]=height[rank[i]]，也就是Suffix[i]和它前一名的最長(zhǎng)公共前綴，那么很明顯有h[i]>=h[i-1]-1。因?yàn)閔[i-1]是Suffix[i-1]和它前一名的最長(zhǎng)公共前綴，設(shè)為Suffix[k]，那么Suffix[i]和Suffix[k+1] 的最長(zhǎng)公共前綴為h[i-1]-1，所以h[i]至少是h[i-1]-1。所以我們可以按照求h[1],h[2],h[3] 順序計(jì)算所有的height。代碼如下

//by司徒正美
function getHeight(str, sa){
    var n = str.length, k = 0, rank = [], height = []
    for(var i = 1;i<=n;i++) {
        rank[sa[i]]=i;
    }
    for(var i=0;i
DC3算法
DC3算法(Difference Cover mod 3)是J. K?rkk?inen和P. Sanders在2003年發(fā)表的論文 "Simple Linear Work Suffix Array Construction"中描述的線性時(shí)間內(nèi)構(gòu)造后綴數(shù)組的算法。詳見(jiàn)下文
http://spencer-carroll.com/th...
太難了，略過(guò)。 此外還有其他構(gòu)造算法，如SA-IS：
https://zhuanlan.zhihu.com/p/... 
我應(yīng)該是搞錯(cuò)學(xué)習(xí)順序了，應(yīng)該先學(xué)hash樹(shù)再學(xué)trie樹(shù)再學(xué)壓縮樹(shù)再學(xué)后綴樹(shù)再學(xué)后綴自動(dòng)機(jī)。即便我頭腦這么好使，跨度這么大，還是碰得一臉灰的。
參考鏈接

http://blog.csdn.net/sojisub_...
http://blog.csdn.net/yxuanwke...

https://wenku.baidu.com/view/... (PPT)