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

• 作者: 张文睿 朱祥彬 袁哲 赵东伟 赵永哲
• 来源期刊: 吉林大学学报（理学版）
• 学科: 工学
• 关键词: 重复(子串) 后缀数组 水平分割法
• 年，卷（期）: 2008,（5）
• 所属期刊栏目: 计算机科学
• 页码范围: 915-924
• 页数: 10页
• 分类号: TP301
• 字数: 7520字
• 语种: 中文
• DOI: 10.3321/j.issn:1671-5489.2008.05.022

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	赵永哲	吉林大学计算机科学与技术学院	29	115	8.0	9.0
2	袁哲	吉林大学计算机科学与技术学院	34	75	6.0	7.0
3	朱祥彬	吉林大学计算机科学与技术学院	2	8	1.0	2.0
4	赵东伟	吉林大学计算机科学与技术学院	1	1	1.0	1.0