Skip to Main content Skip to Navigation
Conference papers

Longest Motifs with a Functionally Equivalent Central Block

Abstract : This paper presents a generalization of the notion of longest repeats with a block of k don't care symbols introduced by [Crochemore et al., LATIN 2004] (for k fixed) to longest motifs composed of three parts: a first and last that parameterize match (that is, match via some symbol renaming, initially unknown), and a functionally equivalent central block. Such three-part motifs are called longest block motifs. Different types of functional equivalence, and thus of matching criteria for the central block are considered, which include as a subcase the one treated in [Crochemore et al., LATIN 2004] and extend to the case of regular expressions with no Kleene closure or complement operation. We show that a single general algorithmic tool that is a non-trivial extension of the ideas introduced in [Crochemore et al., LATIN 2004] can handle all the various kinds of longest block motifs defined in this paper. The algorithm complexity is, in all cases, in O(n log n).
Document type :
Conference papers
Complete list of metadata

Cited literature [22 references]  Display  Hide  Download
Contributor : Maxime Crochemore Connect in order to contact the contributor
Submitted on : Monday, July 15, 2013 - 7:30:32 PM
Last modification on : Saturday, January 15, 2022 - 3:58:14 AM
Long-term archiving on: : Wednesday, October 16, 2013 - 4:12:29 AM


Files produced by the author(s)



Maxime Crochemore, Raffaele Giancarlo, Marie-France Sagot. Longest Motifs with a Functionally Equivalent Central Block. SPIRE'2004, Oct 2004, Padova, Italy. pp.298-309, ⟨10.1007/978-3-540-30213-1_42⟩. ⟨hal-00619978⟩



Record views


Files downloads