AN ONLINE STRING SUPERPRIMITIVITY TEST

被引：67

作者：

BRESLAUER, D ^{[1
]}

机构：

[1] COLUMBIA UNIV,DEPT COMP SCI,NEW YORK,NY 10027

来源：

INFORMATION PROCESSING LETTERS | 1992年 / 44卷 / 06期

关键词：

ANALYSIS OF ALGORITHMS; STRING MATCHING; PERIOD; QUASI-PERIOD; SUPER-PRIMITIVITY;

D O I：

10.1016/0020-0190(92)90111-8

中图分类号：

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

学科分类号：

0812 ;

摘要：

A string w covers another string z if every symbol of z is within some occurrence of w in z. A string is called superprimitive if it is covered only by itself. and quasiperiodic if it is covered by some shorter string. We present an on-line linear-time algorithm that tests if each prefix of an input string is superprimitive while the string is given a symbol at a time.

引用

页码：345 / 347

页数：3