精华内容
下载资源
问答
  • 后缀树

    2019-12-23 17:08:37
    相对于字典树来说,后缀树并不是针对大量字符串的,而是针对一个或几个字符串来解决问题。比如字符串的回文子串,两个字符串的最长公共子串等等,后面应用会说。 一、建立后缀树 比如单词banana,它的所有后缀.....

    转载自:https://blog.csdn.net/dustin_cds/article/details/79729085

     

    后缀树

    就是把一串字符的所有后缀保存并且压缩的字典树。相对于字典树来说,后缀树并不是针对大量字符串的,而是针对一个或几个字符串来解决问题。比如字符串的回文子串,两个字符串的最长公共子串等等,后面应用会说。

     

    一、建立后缀树

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

     

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

     

    后缀树是把一个字符串所有后缀压缩并保存的字典树,所以我们把字符串的所有后缀还是按照字典树的规则建立,就成了上图的样子。 注意还是和字典树一样,根节点必须为空。

    二、压缩后缀树

    下面说下更加节省空间的方案,也就是上面提到的压缩。

     

    因为有些后缀串可能是单串,并不和其他的共用同一个前缀。

    比如上图中的banana这个后缀串,直接可以用1来表示起点,终点是默认的。

    上图的a节点后面有两个节点标记3和5是右边字符数组的下标,对应着a->3-7,a->5-7。因为a是共有的前缀。

     

    三、应用

    https://blog.csdn.net/heyuchang666/article/details/49784201

    如果在后缀树T中查找子串P,我们需要这样的过程:

    (1) 从根结点root出发,遍历所有的根的孩子结点:N1,N2,N3….

    (2) 如果所有孩子结点中的关键字的第一个字符都和P的第一个字符不匹配,则没有这个子串,查找结束。

    (3) 假如N3结点的关键字K3第一个字符与P的相同,则匹配K3和P。

    若 K3.length>=P.length 并且K3.subString(0,P.length-1)=P,则匹配成功,否则匹配失败。

    若 K3.length<=P.length 并且K3=P.subString(0, K3.length-1),则将子串P1=P.subString(K3.length, P.length); 即取出P中排除K3之后的子串。然后P1以N3为根结点继续重复(1)~(3)的步骤。直到匹配完P1的所有字符,则匹配成功。否则匹配失败。

     

    查询效率:很显然,在上面的算法中。匹配成功正好比较了P.length次字符。而定位结点的孩子指针,和Trie情况类似,假如字母表数量为d。则查询效率为O(d*m),实际上,d是固定常数,如果使用Hash表直接定位,则d=1.因此,后缀树查询子串P的时间复杂度为O(m),其中m为P的长度。

     

    3.2 获得字符串s1在字符串s2中重复的次数

    比如说banana是s1,an是s2,那么计算an出现的次数实际上就是看an是几个后缀串的前缀。

    a节点是保存所有起始为a字母的后缀串,我们看a字母后的n字母的引用计数即可。

     

    3.3 两个字符串S1,S2的最长公共部分

    先说下广义后缀树,前面说了后缀树可以存储一个或多个字符串,当存储的字符串数量大于等于2时就叫做广义后缀树。

    建立一棵广义后缀树,如下图:

     

    $和#是为了区分字符串的。

     

    我们为每个后缀串末尾单独添加一个空间存储区分字符串的符号。那么怎么找s1和s2串最长的公共部分?

    遍历每个后缀串,如果其引用计数为1则直接跳过,因为不可能有两个子串存放在这里,当引用计数>1时,往下遍历,直到分叉分别记录子串的符号,如果不同,说明他们是不同字符串的,记录已经匹配的值即可,若相同继续下一次遍历。上图的ana部分,到ana时,子串$结束,然后继续向下,子串anab以#结束,那么匹配了ana。

     

    3.4 最长回文串

     

    回文串有一个定义就是正反相同,也就是正着和反着可以重和在一起,那么我们直接看这棵广义后缀树的共同前缀即可,每个banana的子串和ananab的子串重合的部分都是回文串,我们只需要找到最长的即可。比如上面的anana,从后面不同的标记可以看出两个字符串的某个后缀都有这个前缀,能完美重合到一起。即它是回文串。

    记录Max,每次找到一个回文串比较即可。

     

    四、代码实现

    https://blog.csdn.net/dustin_cds/article/details/79729085

     

    展开全文
  • 经典的后缀树入门,后缀树组稍后共享,从零开始学数据结构。

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 5,943
精华内容 2,377
关键字:

后缀树