Efficient string-matching allowing for non-overlapping inversions

DOI10.1016/j.tcs.2012.06.009zbMath1292.68178OpenAlexW2099839938MaRDI QIDQ390885

Simone Faro, Domenico Cantone, Salvatore Cristofaro

Publication date: 9 January 2014

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2012.06.009

zbMATH Keywords

information retrievalapproximate string matchingaverage complexity analysistext processing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computing methodologies for image processing (68U10) Protein sequences, DNA sequences (92D20) Algorithms on strings (68W32)

Related Items (10)

On pattern matching with \(k\) mismatches and few don't cares ⋮ Duplications and Pseudo-Duplications ⋮ State complexity of inversion operations ⋮ Rich words in the block reversal of a word ⋮ Text searching allowing for inversions and translocations of factors ⋮ Non-overlapping inversion on strings and languages ⋮ Block reversal on finite words ⋮ Pseudo-inversion: closure properties and decidability ⋮ An efficient algorithm for computing non-overlapping inversion and transposition distance ⋮ Alignment with non-overlapping inversions and translocations on two strings

Cites Work

• Unnamed Item
• Simple and efficient string matching with k mismatches
• A local algorithm for DNA sequence alignment with inversions
• A space-efficient algorithm for sequence alignment with inversions and reversals
• String matching with inversions and translocations in linear average time (most of the time)
• New and faster filters for multiple approximate string matching

This page was built for publication: Efficient string-matching allowing for non-overlapping inversions