基于广义后缀树的最长重复子模式算法

最长重复子串问题是字符串处理中的一个经典问题,是许多应用的基础。但有些时候人们不只关心相等的子串对,还要查找具有某种其他关系的子串对。例如在DNA序列中通常关心字符串和它的补串。这种联系可以看成是一个字符串经过某种置换后与另一个字符串相等。因此本文定义了单一置换下的最长重复子模式和最长重复子模式两个问题,提出了基于广义后缀树的算法来解决这两个问题,并在理论上分析了它们的时间复杂性和空间复杂性。

Algorithm of Finding Maximal Repetitive Pattern Based on General Suffix Tree

Finding the maximal repeat is a classic problem in the field of string processing.In some application,we are concerned not only with the substrings which are equal,but also with the substring which is equal to another substring under some permutation.For example,in DNA sequence,we are usually concerned with the subsequence and its complement.In this paper,we present the problem of finding maximal repetitive pattern.We make a precise definition of the problem of finding maximal repetitive pattern,also with the problem of finding maximal repetitive pattern under a permutation.We propose the algorithms based on general suffix tree to solve them and make the analysis of their time complexity and space complexity.