Parallel detection of all palindromes in a string

DOI10.1016/0304-3975(94)00083-UzbMATH Open0873.68039OpenAlexW1969073904WikidataQ56550632 ScholiaQ56550632MaRDI QIDQ673783FDOQ673783

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

Searching and sorting (68P10)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The equation \(a_ M=b^ Nc^ P\) in a free group
• Finding all periods and initial palindromes of a string in parallel
• Fast Pattern Matching in Strings
• The Parallel Evaluation of General Arithmetic Expressions
• A New Linear-Time ``On-Line Algorithm for Finding the Smallest Initial Palindrome of a String
• Palindrome recognition in real time by a multitape Turing machine
• A Linear-Time On-Line Recognition Algorithm for ``Palstar
• Usefulness of the Karp-Miller-Rosenberg algorithm in parallel computations on strings and arrays
• Optimal parallel algorithms for periods, palindromes and squares
• Recognizing a symmetry predicate by multihead Turing machines with input
• Two fast simulations which imply some fast string matching and palindrome-recognition algorithms
• An Optimal $O(\log\log n)$ Time Parallel String Matching Algorithm
• Optimal parallel algorithms for string matching

Cited In (27)

• Counting distinct palindromes in a word in linear time
• Longest substring palindrome after edit
• Palindromic decompositions with gaps and errors
• A subquadratic algorithm for minimum palindromic factorization
• Quantum algorithm for learning secret strings and its experimental demonstration
• Efficient algorithms to compute compressed longest common substrings and compressed palindromes
• Parallel finding all initial palindromes and periods of a string on reconfigurable meshes
• Comparing Degenerate Strings
• Detecting regularities on grammar-compressed strings
• Computing Longest Single-arm-gapped Palindromes in a String
• Fast algorithms for the shortest unique palindromic substring problem on run-length encoded strings
• Minimal unique palindromic substrings after single-character substitution
• Computing longest palindromic substring after single-character or block-wise edits
• Finding approximate palindromes in strings
• Finding Gapped Palindromes Online
• Maximal degenerate palindromes with gaps and mismatches
• Faster queries for longest substring palindrome after block edit
• Palindromic Decompositions with Gaps and Errors
• Efficient computation of longest single-arm-gapped palindromes in a string
• Tight tradeoffs for real-time approximation of longest palindromes in streams
• On finding a longest common palindromic subsequence
• Title not available (Why is that?)
• Finding top-\(k\) longest palindromes in substrings
• EERTREE: an efficient data structure for processing palindromes in strings
• Computing Longest Common Substring and All Palindromes from Compressed Strings
• Efficient string matching on packed texts
• Data structures for computing unique palindromes in static and non-static strings

This page was built for publication: Parallel detection of all palindromes in a string

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q673783)