摘要
基于自顶向下的后缀树建立思想,提出一种分步建立后缀树的方法。首先对字符串中所有后缀按照字母表顺序进行排序,然后求出有序相邻后缀之间的最长公共前缀,并根据后缀顺序和最长公共前缀建立后缀树。该方法无需使用后缀链,并且可以在线性时间建立后缀树。
A top-down method of construction for suffix trees step by step is presented. Firstly, all the suffixes of a string are sorted by sorting according to lexicographical order. Secondly, the longest common prefixes of all pairs of adjacent suffixes on the suffix array between them are computed. Finally, suffix trees are constructed based on the suffix order and the longest common prefixes of all pairs of adjacent suffixes. This method saves the need for the suffix -links.
出处
《电子科技》
2013年第10期73-75,共3页
Electronic Science and Technology
