利用水平分割法计算给定串中的所有Maximal(NE/SNE) Repeats  

Compute All Maximal(NE/SNE) Repeats in a String with Horizontal-division Method

作　　者：袁哲[1] 赵永哲[1] 张文睿 朱祥彬[1] 赵东伟[1] 

机构地区：[1]吉林大学计算机科学与技术学院,长春130012 [2]吉林移动通信有限公司吉林市分公司,吉林吉林132001

出　　处：《吉林大学学报（理学版）》2008年第5期915-924,共10页Journal of Jilin University:Science Edition

基　　金：国家自然科学基金(批准号:60373097)

摘　　要：提出一种利用给定符号串x[1…n]的后缀数组和最长公共前缀数组求x所有最大重复的新方法水平分割法.通过对x的最大不可扩展重复和最大超级不可扩展重复所有可能出现的位置以及判定条件的提炼,分别给出仅由x的后缀数组和最长公共前缀数组求x的所有最大重复、最大不可扩展重复和最大超级不可扩展重复的算法.该算法克服了除后缀数组和最长公共前缀数组外,还需利用其他辅助数组的缺陷,降低了空间开销,且时间复杂度没有增加,并可以在对最长公共前缀数组仅进行一次扫描的情况下求出给定串的所有最大重复、最大不可扩展重复和最大超级不可扩展重复.We proposed a new method-horizontal-division method by which we can compute all the Maximal Repeats of string x using only suffix array SAx and LCP array LCPx. We analyzed the situations and locations where the Maximal NE-Repeats and SNE-Repeats of x can be. Then we designed three algorithms by which all Maximal Repeats, Maximal NE-Repeats, and Maximal SNE-Repeats in a string x [1…n] can be computed only by means of SAx and LCPx. The given algorithms overcome the defects of the corresponding algorithms which require other assistant arrays in addition to suffix array and LCP array. So our algorithms reduce the space requirement greatly. Moreover, the time complexity of these algorithms is not increased. In addition, we can get all the Maximal Repeats, Maximal NE Repeats and Maximal SNE Repeats of a string by only scanning LCP array once.

关 键 词：重复(子串) 后缀数组 水平分割法 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]