EFFICIENT DETECTION OF QUASIPERIODICITIES IN STRINGS

被引：62

作者：

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 条

[1]

Aho A. V., 1974, DESIGN ANAL COMPUTER

[2] OPTIMAL PARALLEL DETECTION OF SQUARES IN STRINGS [J].