Parallel detection of all palindromes in a string

DOI10.1016/0304-3975(94)00083-UzbMath0873.68039WikidataQ56550632 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

zbMATH Keywords

palindromes

Mathematics Subject Classification ID

68P10: Searching and sorting

Related Items

Efficient string matching on packed texts, Comparing Degenerate Strings, Faster queries for longest substring palindrome after block edit, Longest substring palindrome after edit, Palindromic Decompositions with Gaps and Errors, Computing Longest Common Substring and All Palindromes from Compressed Strings, 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, Efficient algorithms to compute compressed longest common substrings and compressed palindromes, Parallel finding all initial palindromes and periods of a string on reconfigurable meshes, On finding a longest common palindromic subsequence, Finding approximate palindromes in strings, Fast algorithms for the shortest unique palindromic substring problem on run-length encoded strings, Quantum algorithm for learning secret strings and its experimental demonstration, Minimal unique palindromic substrings after single-character substitution, Computing longest palindromic substring after single-character or block-wise edits, Efficient computation of longest single-arm-gapped palindromes in a string, Tight tradeoffs for real-time approximation of longest palindromes in streams, Palindromic decompositions with gaps and errors, Detecting regularities on grammar-compressed strings, Finding Gapped Palindromes Online, Computing Longest Single-arm-gapped Palindromes in a String

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