Usefulness of the Karp-Miller-Rosenberg algorithm in parallel computations on strings and arrays

DOI10.1016/0304-3975(91)90073-BzbMath0737.68037DBLPjournals/tcs/CrochemoreR91WikidataQ56814566 ScholiaQ56814566MaRDI QIDQ1177175

Wojciech Rytter, Maxime Crochemore

Publication date: 26 June 1992

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

stringsparallel complexitypattern matchingpatternCRCW-PRAMCREW-PRAM

Mathematics Subject Classification ID

Distributed algorithms (68W15)

Related Items (21)

On two-dimensional pattern matching by optimal parallel algorithms ⋮ Multidimensional period recovery ⋮ Finding all periods and initial palindromes of a string in parallel ⋮ An efficient algorithm for online square detection ⋮ Longest Gapped Repeats and Palindromes ⋮ Longest $$\alpha $$-Gapped Repeat and Palindrome ⋮ Fast parallel Lyndon factorization with applications ⋮ Tighter bounds and optimal algorithms for all maximal \(\alpha\)-gapped repeats and palindromes. Finding all maximal \(\alpha\)-gapped repeats and palindromes in optimal worst case time on integer alphabets ⋮ Efficient string matching on packed texts ⋮ Detecting the morphic images of a word : improving the general algorithm ⋮ New simple efficient algorithms computing powers and runs in strings ⋮ Parallel detection of all palindromes in a string ⋮ Efficient computation of maximal anti-exponent in palindrome-free strings ⋮ Optimal parallel detection of squares in strings ⋮ Efficient detection of quasiperiodicities in strings ⋮ Finding all the palindromes in a binary tree in linear time and space ⋮ Forty Years of Text Indexing ⋮ Optimal parallel algorithms for periods, palindromes and squares ⋮ Masking patterns in sequences: A new class of motif discovery with don't cares ⋮ Alphabet-independent optimal parallel search for three-dimensional patterns ⋮ Parallel construction and query of index data structures for pattern matching on square matrices

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Parallel construction of a suffix tree with applications
• An optimal algorithm for computing the repetitions in a word
• Transducers and repetitions
• A note on optimal parallel transformations of regular expressions to nondeterministic finite automata
• Time-space-optimal string matching
• A fast string searching algorithm
• Factorizing words over an ordered alphabet
• An O(n log n) algorithm for finding all repetitions in a string
• Optimal parallel algorithms for string matching
• Optimal parallel pattern matching in strings
• Efficient string matching
• A New Linear-Time ``On-Line Algorithm for Finding the Smallest Initial Palindrome of a String
• A Linear-Time On-Line Recognition Algorithm for ``Palstar
• Fast Pattern Matching in Strings
• A Technique for Extending Rapid Exact-Match String Matching to Arrays of More than One Dimension
• Correction: Parallel Merge Sort
• Two-way string-matching

This page was built for publication: Usefulness of the Karp-Miller-Rosenberg algorithm in parallel computations on strings and arrays