Efficient string-matching allowing for non-overlapping inversions

DOI10.1016/j.tcs.2012.06.009zbMath1292.68178MaRDI 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 retrieval; approximate string matching; average complexity analysis; text processing

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68U10: Computing methodologies for image processing

92D20: Protein sequences, DNA sequences

68W32: Algorithms on strings

Related Items

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

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