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

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