EFFICIENT DETECTION OF QUASIPERIODICITIES IN STRINGS

被引：60
作者：
APOSTOLICO, A
EHRENFEUCHT, A
机构：
[1] UNIV PADUA,DIPARTIMENTO ELETTRON & INFORMAT,PADUA,ITALY
[2] UNIV COLORADO,DEPT COMP SCI,BOULDER,CO 80301
来源：
THEORETICAL COMPUTER SCIENCE | 1993年 / 119卷 / 02期
关键词：
D O I：
10.1016/0304-3975(93)90159-Q
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
A string z is quasiperiodic if there is a second string w not-equal z such that the occurrences of w in z cover z entirely, i.e., every position of z falls within some occurrence of w in z. It is shown here that all maximal quasiperiodic substrings of a string x of n symbols can be detected in time O(n log2 n).
引用
收藏
页码：247 / 265
页数：19
相关论文
共 20 条
12