Optimal pattern matching on meshes

Bogdan S. Chlebus, Leszek Gąsieniec

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

2 Scopus citations


Parallel pattern matching on a mesh-connected array of processors is considered. The problem is to find all occurrences of a pattern in a text. The input text is a string of n symbols placed in a √n×√n mesh, each processor storing one symbol. The pattern is stored similarly in a contiguous portion of the mesh. An algorithm solving the problem in time O(√n) is presented. It applies a novel technique to design parallel pattern-matching algorithms based on the notion of a pseudo-period.

Original languageEnglish (US)
Title of host publicationSTACS 1994 - 11th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings
EditorsErnst W. Mayr, Klaus W. Wagner, Patrice Enjalbert
PublisherSpringer Verlag
Number of pages12
ISBN (Print)9783540577850
StatePublished - Jan 1 1994
Externally publishedYes
EventProceedings of the 11th Symposium on Theoretical Aspects of Computer Science (STACS'94) - Caen, Fr
Duration: Feb 24 1994Feb 26 1994

Publication series

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


ConferenceProceedings of the 11th Symposium on Theoretical Aspects of Computer Science (STACS'94)
CityCaen, Fr

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Optimal pattern matching on meshes'. Together they form a unique fingerprint.

Cite this