Finding all periods and initial palindromes of a string in parallel

DOI10.1007/BF01294132zbMath0833.68053OpenAlexW2244342551MaRDI QIDQ1899224

Zvi Galil, Dany Breslauer

Publication date: 11 March 1996

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01294132

zbMATH Keywords

CRCW-PRAM algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics on words (68R15) Parallel algorithms in computer science (68W10) Distributed algorithms (68W15)

Related Items

Palindromic subsequence automata and longest common palindromic subsequence, Transforming comparison model lower bounds to the parallel-random-access-machine, Time-Space Trade-Offs for Longest Common Extensions, Palindromic decompositions with gaps and errors, String powers in trees, Counting distinct palindromes in a word in linear time, Searching for Gapped Palindromes, Efficient retrieval of approximate palindromes in a run-length encoded string, Efficient string matching on packed texts, Time-space trade-offs for longest common extensions, Palindromic Decompositions with Gaps and Errors, Parallel detection of all palindromes in a string, Fast parallel string prefix-matching, Optimal parallel algorithms for periods, palindromes and squares, Parallel finding all initial palindromes and periods of a string on reconfigurable meshes, Searching for gapped palindromes, Finding approximate palindromes in strings, Testing string superprimitivity in parallel

Cites Work

• Fast parallel string prefix-matching
• The equation \(a_ M=b^ Nc^ P\) in a free group
• Usefulness of the Karp-Miller-Rosenberg algorithm in parallel computations on strings and arrays
• An on-line string superprimitivity test
• Testing string superprimitivity in parallel
• An Optimal $O(\log\log n)$ Time Parallel String Matching Algorithm
• Optimal parallel algorithms for string matching
• Optimal parallel pattern matching in strings
• A Lower Bound for Parallel String Matching
• A New Linear-Time ``On-Line Algorithm for Finding the Smallest Initial Palindrome of a String
• Parallelism in Comparison Problems
• Fast Pattern Matching in Strings
• The Parallel Evaluation of General Arithmetic Expressions
• Parallel Suffix–Prefix-Matching Algorithm and Applications
• An Optimal $O(\log \log N)$-Time Parallel Algorithm for Detecting all Squares in a String
• Unnamed Item
• Unnamed Item
• Unnamed Item