Finding all periods and initial palindromes of a string in parallel
From MaRDI portal
Publication:1899224
DOI10.1007/BF01294132zbMath0833.68053MaRDI QIDQ1899224
Publication date: 11 March 1996
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01294132
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