๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Optimal parallel algorithms for string matching

โœ Scribed by Zvi Galil

Book ID
114037740
Publisher
Elsevier Science
Year
1985
Weight
744 KB
Volume
67
Category
Article
ISSN
0019-9958

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

Simple Optimal String Matching Algorithm
Simple Optimal String Matching Algorithm
โœ Cyril Allauzen; Mathieu Raffinot ๐Ÿ“‚ Article ๐Ÿ“… 2000 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 140 KB

We present a new string matching algorithm optimal on average (with equiprobability and independence of letters, in O m + n log m/m , where n is the size of the text and m the size of the searched word, both taken on an alphabet ) and linear in the worst case (in O m + n ). Of all the algorithms tha

Derivation of a parallel string matching
Derivation of a parallel string matching algorithm
โœ Jayadev Misra ๐Ÿ“‚ Article ๐Ÿ“… 2003 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 67 KB

We derive an efficient parallel algorithm to find all occurrences of a pattern string in a subject string in O(log n) time, where n is the length of the subject string. The number of processors employed is of the order of the product of the two string lengths.