Parallel detection of all palindromes in a string
From MaRDI portal
Publication:673783
DOI10.1016/0304-3975(94)00083-UzbMath0873.68039OpenAlexW1969073904WikidataQ56550632 ScholiaQ56550632MaRDI QIDQ673783
Zvi Galil, Alberto Apostolico, Dany Breslauer
Publication date: 28 February 1997
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(94)00083-u
Related Items
Minimal unique palindromic substrings after single-character substitution ⋮ Palindromic decompositions with gaps and errors ⋮ Finding top-\(k\) longest palindromes in substrings ⋮ Maximal degenerate palindromes with gaps and mismatches ⋮ A subquadratic algorithm for minimum palindromic factorization ⋮ Counting distinct palindromes in a word in linear time ⋮ Data structures for computing unique palindromes in static and non-static strings ⋮ On finding a longest common palindromic subsequence ⋮ Computing Longest Single-arm-gapped Palindromes in a String ⋮ Efficient string matching on packed texts ⋮ Palindromic Decompositions with Gaps and Errors ⋮ Computing longest palindromic substring after single-character or block-wise edits ⋮ Computing Longest Common Substring and All Palindromes from Compressed Strings ⋮ Fast algorithms for the shortest unique palindromic substring problem on run-length encoded strings ⋮ Detecting regularities on grammar-compressed strings ⋮ Efficient algorithms to compute compressed longest common substrings and compressed palindromes ⋮ Efficient computation of longest single-arm-gapped palindromes in a string ⋮ Parallel finding all initial palindromes and periods of a string on reconfigurable meshes ⋮ Finding Gapped Palindromes Online ⋮ Faster queries for longest substring palindrome after block edit ⋮ Comparing Degenerate Strings ⋮ Tight tradeoffs for real-time approximation of longest palindromes in streams ⋮ Finding approximate palindromes in strings ⋮ Quantum algorithm for learning secret strings and its experimental demonstration ⋮ Longest substring palindrome after edit
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- 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
- Recognizing a symmetry predicate by multihead Turing machines with input
- Two fast simulations which imply some fast string matching and palindrome-recognition algorithms
- Palindrome recognition in real time by a multitape Turing machine
- Finding all periods and initial palindromes of a string in parallel
- An Optimal $O(\log\log n)$ Time Parallel String Matching Algorithm
- Optimal parallel algorithms for 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
- The Parallel Evaluation of General Arithmetic Expressions
- Optimal parallel algorithms for periods, palindromes and squares
