@inproceedings{5df2fb1e8b77406ea048b4bd54629393,

title = "Optimal pattern matching on meshes",

abstract = "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.",

author = "Chlebus, {Bogdan S.} and Leszek G{\c a}sieniec",

year = "1994",

month = jan,

day = "1",

language = "English (US)",

isbn = "9783540577850",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "213--224",

editor = "Mayr, {Ernst W.} and Wagner, {Klaus W.} and Patrice Enjalbert",

booktitle = "STACS 1994 - 11th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings",

note = "Proceedings of the 11th Symposium on Theoretical Aspects of Computer Science (STACS'94) ; Conference date: 24-02-1994 Through 26-02-1994",

}