Efficient string matching on coded texts

Dany Breslauer, Leszek Gąsieniec

Research output: Chapter in Book/Report/Conference proceedingConference contribution


The so called "four Russians technique" is often used to speed up algorithms by encoding several data items in a single memory cell. Given a sequence of n symbols over a constant size alphabet, one can encode the sequence into O(n/A) memory cells in O(log A) time using n~ log A processors. This paper presents an efficient CRCW-PRAM string-matching algorithm for coded texts that takes O(loglog(m/),)) time4 making only O(n/A) operations, an improvement by a factor of A --- O(log n) on the number of operations used in previous algorithms. Using this stringmatching algorithm one can test if a string is square-free and find all palindromes in a string in O(log log n) time using n~ log log n processors.

Original languageEnglish (US)
Title of host publicationCombinatorial Pattern Matching - 6th Annual Symposium, CPM 1995, Proceedings
EditorsZvi Galil, Esko Ukkonen
PublisherSpringer Verlag
Number of pages13
ISBN (Print)3540600442, 9783540600442
StatePublished - 1995
Externally publishedYes
Event6th Annual Symposium on Combinatorial Pattern Matching, CPM 1995 - Espoo, Finland
Duration: Jul 5 1995Jul 7 1995

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference6th Annual Symposium on Combinatorial Pattern Matching, CPM 1995

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Efficient string matching on coded texts'. Together they form a unique fingerprint.

Cite this