后缀树/后缀数组

- 日理万妓 2022-05-15 14:20 249阅读 0赞

字典树：[https://blog.csdn.net/hebtu666/article/details/83141560][https_blog.csdn.net_hebtu666_article_details_83141560]

### 后缀树：后缀树，就是把一串字符的所有后缀保存并且压缩的字典树。 ###

###  ###

### 相对于字典树来说，后缀树并不是针对大量字符串的，而是针对一个或几个字符串来解决问题。比如字符串的回文子串，两个字符串的最长公共子串等等。 ###

比如单词banana，它的所有后缀显示到下面的。0代表从第一个字符为起点，终点不用说都是字符串的末尾。

以上面的后缀，我们建立一颗后缀树。如下图，为了方便看到后缀，我没有合并相同的前缀。

![Center][]

把非公共部分压缩：

![Center 1][]

![Center 2][]

后缀树的应用：

（1）查找某个字符串s1是否在另外一个字符串s2中：如果s1在字符串s2中，那么s1必定是s2中某个后缀串的前缀。

（2）指定字符串s1在字符串s2中重复的次数：比如说banana是s1，an是s2，那么计算an出现的次数实际上就是看an是几个后缀串的前缀。

（3）两个字符串S1，S2的最长公共部分（广义后缀树）

（4）最长回文串（广义后缀树）

关于后缀树的实现和应用以后再写，这次主要写后缀数组。

在字符串处理当中，后缀树和后缀[数组][Link 1]都是非常有力的工具。其实后缀数组是后缀树的一个非常精巧的替代品，它比后缀树容易编程实现，能够实现后缀树的很多功能而时间复杂度也不太逊色，并且，它比后缀树所占用的空间小很多。可以说，在信息学竞赛中后缀数组比后缀树要更为实用。

### 后缀数组：就是把某个字符串的所有后缀按照字典序排序后的数组。（数组中保存起始位置就好了，结束位置一定是最后） ###

先说如何计算后缀数组：

倍增的思想，我们先把每个长度为2的子串排序，再利用结果把每个长度为4的字串排序，再利用结果排序长度为8的子串。。。直到长度大于等于串长。

设置sa\[\]数组来记录排名：sa\[i\]代表排第i名的是第几个串。

结果用rank\[\]数组返回，rank\[i\]记录的是起始位置为第i个字符的后缀排名第几小。

我们开始执行过程：

比如字符串abracadabra

长度为2的排名：a ab ab ac ad br br ca da ra ra,他们分别排第0，1，2，2，3，4，5，5，6，7，8，8名

sa数组就是11(空串),10(a),0(ab),7,3,5,1,8,4,6,2,9(ra排名最后)

这样，所有长度为2的子串的排名就出来了，我们如何利用排名把长度为4的排名搞出来呢？

abracadabra中，ab,br,ra这些串排名知道了。我们把他们两两合并为长度为4的串，进行排名。

比如abra和brac怎么比较呢？

用原来排名的数对来表示

abra=ab+ra=1+8

brac=br+ac=4+2

对于字符串的字典序，这个例子比1和4就比出来了。

如果第一个数一样，也就是前两个字符一样，那再比后面就可以了。

简单说就是先比前一半字符的排名，再比后一半的排名。

具体实现，我们可以用系统sort，传一个比较器就好了。

还有需要注意，长度不可能那么凑巧是2^n，所以 一般的，k=n时，rank\[i\]表示从位置i开始向后n个字符的排名第几小，而剩下不足看个字符，rank\[i\]代表从第i个字符到最后的串的排名第几小，也就是后缀。

保证了每一个后缀都能正确表示并排序。比如k=4时，就表示出了长度为1，2，3的后缀：a,ra,bra.这就保证了k=8时，长度为5，6，7的后缀也能被表示出来：4+1，4+2，4+3

还有，sa\[0\]永远是空串，空串的排名rank\[sa\[0\]\]永远是最大。

int n;
    int k;
    int rank[MAX_N+1];//结果（排名）数组
    int tmp[MAX_N+1];//临时数组
    //定义比较器
    bool compare(int i,int j)
    {
        if(rank[i]!=rank[j])return rank[i]<rank[j];
        //长度为k的子串的比较
        int ri=i+k<=n ? rank[i+k] : -1;
        int rj=j+k<=n ? rank[j+k] : -1;
        return ri<rj;
    }
    
    void solve(string s,int *sa)
    {
        n=s.length;
        //长度为1时，按字符码即可，长度为2时就可以直接用
        for(int i=0;i<=n;i++)
        {
            sa[i]=i;
            rank[i]=i<n ? s[i] : -1;//注意空串为最大
        }
        //由k对2k排序，直到超范围
        for(k=1;k<=n;k*=2)
        {
            sort(sa,sa+n+1,compare);
            tmp[sa[0]=0;//空串
            for(int i=1;i<=n;i++)
            {
                tmp[sa[i]]=tmp[sa[i-1]]+(compare(sa[i-1],sa[i]) ? 1 : 0);//注意有相同的
            }
            for(int i=0;i<=n;i++)
            {
                rank[i]=tmp[i];
            }
        }
    }

具体应用以后再写。。。。。

[https_blog.csdn.net_hebtu666_article_details_83141560]: https://blog.csdn.net/hebtu666/article/details/83141560
[Center]: /images/20220503/16e71abd633e4a219d1452a8b365b242.png
[Center 1]: /images/20220503/feb28bd8ca06439d8524f6c860e8c812.png
[Center 2]: /images/20220503/0e689b5b95c74bbabb9e867143cca608.png
[Link 1]: https://baike.baidu.com/item/%E6%95%B0%E7%BB%84