Finding all periods and initial palindromes of a string in parallel

DOI10.1007/BF01294132zbMath0833.68053MaRDI 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

68Q25: Analysis of algorithms and problem complexity

68R15: Combinatorics on words

68W10: Parallel algorithms in computer science

68W15: Distributed algorithms

Related Items

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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