论文部分内容阅读
提出一种利用给定符号串x[1…n]的后缀数组和最长公共前缀数组求x所有最大重复的新方法—水平分割法。通过对x的最大不可扩展重复和最大超级不可扩展重复所有可能出现的位置以及判定条件的提炼，分别给出仅由z的后缀数组和最长公共前缀数组求X的所有最大重复、最大不可扩展重复和最大超级不可扩展重复的算法。该算法克服了除后缀数组和最长公共前缀数组外，还需利用其他辅助数组的缺陷，降低了空间开销，且时间复杂度没有增加，并可以在对最长公共前缀数组仅进行一次扫描的情况下求出给定串的所有最大重复、最大不可扩展重复和最大超级不可扩