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

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

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

后綴是字符串從某個位置起到達末尾的一種特殊子串。后綴可以等于自身，相等于從一個字符開始. 假令我們設計一個取后綴的函數, 它可以這樣實現:

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

后綴必須包含最后一個字符.

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

字符串默認的比較算法, "aa" < "ab" 返回true而不是返回false就是依靠這個標準進行.

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

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

后端數組就是某個字符串的所有后綴按照字典順序進行排序后得到的位置數組. 如字符串ADCEFD, 當i從0到5遞增時,我們通過上面的suffix函數得到其所有 后綴.

按字典排序后

這個[0,2,5,1,3,4]就是字符串的后綴數組.

// 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"]
// 對abadefg的所有后綴子串數組進行加工
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，也可以不加，看你的習慣
})
console.log(sa)// [0, 2, 5, 1, 3, 4]

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

整個過程大家可以參考羅穗騫的論文，但由于語言的差異，我看不 懂他在寫什么，直接對著它的那張圖搞出來了。

// by 司徒正美
function getSuffix(str) {
    var len = str.length, 
        max = str.charCodeAt(0), 
        min = max,
        xbuckets = [],
        sa = [],
        rank = [];
    // 將用戶傳入的字符串全部轉換為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);
    }
    //我們要對rank進行計數排序，但是它們太大，都是90－128左右，
    // 這樣我們要創建上百個桶
    //我們通過減去最小值，來縮小規模, 現在只需2－10個桶就夠了。

    //這些新得到的數字其實在原論文中構成一個叫 x 的數組
    //但是我們并沒有這樣用，而是讓它作為rank對象數組的一個屬性
    rank.forEach(function(el, i){
        rank[i] = {x: el - min + 1 };
    });
  
    var hasDuplicate = true, k = 0;
    while(hasDuplicate){
        //重置數據
        hasDuplicate = false;
        xbuckets.length = 0;
        //k倍增，隔空拼湊y數組
        //y作為基數排序的第二個關鍵字
        var d = 1 << k; k ++;
        rank.forEach(function(el, i){
            el.y = rank[i+ d] ? rank[i+ d].x: 0;
        });
        //根據關鍵字x，進行基數排序
        rank.forEach(function(el){
            var index = el.x;
            if(!xbuckets[index]){
                xbuckets[index] = [el];
            }else{
                xbuckets[index].push(el);
            }
        });
        //對每個桶內xbucket根據y進行排序
        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開始的，因此這里面要減1
    rank = rank.map(function(el, i ){
        sa[el.x - 1] = i;
        return el.x;
    });
    console.log("rank數組", rank);
    console.log("后綴數組", sa);
    return sa;
}

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

但這依賴于原生的sort, 我們可以將sort改成計數排序。

// by 司徒正美
function getSuffix(str) {
    var len = str.length, 
        max = str.charCodeAt(0), 
        min = max,
        xbuckets = [],
        sa = [],
        rank = [];
    // 字符串轉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){
        //重置數據
        hasDuplicate = false;
        xbuckets.length = 0;
        //倍增，目的是求關鍵字y
        var d = 1 << k; k ++;

        rank.forEach(function(el, i){
            //根據關鍵字x，進行基數排序，并同時計算關鍵字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){
                //使用計數排序對每個桶再進行排序
                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開始的，因此這里面要減1
    rank = rank.map(function(el, i ){
        sa[el.x - 1] = i;
        return el.x;
    });
    console.log("rank數組", rank);
    console.log("后綴數組", sa);
    return sa;
}
var a = getSuffix("aabaaaab"); 

那么如何計算height？我們定義h[i]=height[rank[i]]，也就是Suffix[i]和它前一名的最長公共前綴，那么很明顯有h[i]>=h[i-1]-1。因為h[i-1]是Suffix[i-1]和它前一名的最長公共前綴，設為Suffix[k]，那么Suffix[i]和Suffix[k+1] 的最長公共前綴為h[i-1]-1，所以h[i]至少是h[i-1]-1。所以我們可以按照求h[1],h[2],h[3] 順序計算所有的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年發表的論文 "Simple Linear Work Suffix Array Construction"中描述的線性時間內構造后綴數組的算法。詳見下文
http://spencer-carroll.com/th...
太難了，略過。 此外還有其他構造算法，如SA-IS：
https://zhuanlan.zhihu.com/p/... 
我應該是搞錯學習順序了，應該先學hash樹再學trie樹再學壓縮樹再學后綴樹再學后綴自動機。即便我頭腦這么好使，跨度這么大，還是碰得一臉灰的。
參考鏈接

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

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