A fast algorithm for the all-pairs suffix-prefix problem

DOI10.1016/j.tcs.2017.07.013zbMath1380.68479OpenAlexW2738126475MaRDI QIDQ1676303

Jihyuk Lim, Kun Soo Park

Publication date: 6 November 2017

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

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

zbMATH Keywords

DNA sequence assemblyalgorithm engineeringall-pairs suffix-prefix problem

Mathematics Subject Classification ID

Protein sequences, DNA sequences (92D20) Algorithms on strings (68W32)

Related Items

All-pairs suffix/prefix in optimal time using Aho-Corasick space, Hierarchical overlap graph

Uses Software

• Readjoiner

Cites Work

• Replacing suffix trees with enhanced suffix arrays
• Efficient algorithms for the all-pairs suffix-prefix problem and the all-pairs substring-prefix problem
• An efficient algorithm for the all pairs suffix-prefix problem
• Fast practical multi-pattern matching
• Parallel computation for the all-pairs suffix-prefix problem
• An improved algorithm for the all-pairs suffix-prefix problem
• A fast string searching algorithm
• Suffix Arrays: A New Method for On-Line String Searches
• Efficient string matching
• Algorithms on Strings, Trees and Sequences