Istituto di Scienza e Tecnologie dell'Informazione     
Breslauer D. Testing string superprimitivity in parallel. In: Information Processing Letters, vol. 49 (5) pp. 235 - 241. Elsevier, 1994.
A string w couers 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. This paper presents an optimal Ο(α(|z|) log log |z|) time CRCW-PRAM algorithm that tests if a string z is superprimitive, where α(|z|) is the inverse of Ackermann function. An alternative implementation takes Ο(log log |z|) time using (|z|log|z|)/log log|z| processors, and is the fastest possible with this number of processors over a general alphabet.
Subject Parallel algorithms
String matching
F.2.1 Numerical Algorithms and Problems

Icona documento 1) Download Document PDF

Icona documento Open access Icona documento Restricted Icona documento Private


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional