Parallel detection of all palindromes in a string

DOI10.1016/0304-3975(94)00083-UzbMath0873.68039WikidataQ56550632 ScholiaQ56550632MaRDI QIDQ673783

Dany Breslauer, Alberto Apostolico, Zvi Galil

Publication date: 28 February 1997

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

palindromes

Mathematics Subject Classification ID

68P10: Searching and sorting

Related Items

Efficient string matching on packed texts, Computing Longest Common Substring and All Palindromes from Compressed Strings, 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, 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