后缀树的设计与构造

Design and Construction of Suffix Trees

后缀树是处理字符串的一个优秀算法。利用图像化设计可使后缀树更加清晰。按照递推的思路,建立前i个字符对应的后缀树,通过插入第i+1个字符的方式,建立前i+1个字符对应的后缀树。由于字符串的任意子串都可以表示为某个后缀的前缀,因此可以设定当前节点为根节点。父节点取子节点中贡献最大的节点,同时,记录其对应的字符串。

Suffix tree is an excellent algorithm for string processing.The suffix tree can be clearer by image design.According to the recursive thinking,the suffix tree corresponding to the first I characters is established,and the suffix tree corresponding to the first I+1 characters is established by inserting the first I+1 characters.Since any substring of a string can be represented as a prefix of a suffix,the current node can be set as the root node.The parent node takes the node that contributes the most to the child node,and records its corresponding string.