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 metadatas

Cited literature [22 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-00619978
Contributor : Maxime Crochemore <>
Submitted on : Monday, July 15, 2013 - 7:30:32 PM
Last modification on : Thursday, November 21, 2019 - 1:14:17 PM
Long-term archiving on: Wednesday, October 16, 2013 - 4:12:29 AM

File

2004_01.pdf
Files produced by the author(s)

Identifiers

Citation

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⟩

Share

Metrics

Record views

418

Files downloads

256