OPTIMAL SUPERPRIMITIVITY TESTING FOR STRINGS

被引：73

作者：

APOSTOLICO, A

FARACH, M

ILIOPOULOS, CS

机构：

[1] UNIV LAQUILA,DIPARTIMENTO MATEMAT PURA & APPL,I-67100 LAQUILA,ITALY

[2] UNIV MARYLAND,DEPT COMP SCI,COLLEGE PK,MD 20742

[3] UNIV LONDON ROYAL HOLLOWAY & BEDFORD NEW COLL,DEPT COMP SCI,EGHAM TW20 0EX,SURREY,ENGLAND

来源：

INFORMATION PROCESSING LETTERS | 1991年 / 39卷 / 01期

基金：

美国国家科学基金会;

关键词：

COMBINATORIAL PROBLEMS; DESIGN OF ALGORITHMS; ANALYSIS OF ALGORITHMS; ALGORITHMS ON WORDS; SUPERPRIMITIVE STRINGS; PERIOD OF A STRING; QUASIPERIOD OF A STRING;

D O I：

10.1016/0020-0190(91)90056-N

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

A string w covers another string z if every position of z is within some occurrence of w in z. Clearly, every string is covered by itself. A string that is covered only by itself is superprimitive. We show that the property of being superprimitive is testable on a string of n symbols in O(n) time and space.

引用

页码：17 / 20

页数：4