An efficient algorithm for the all pairs suffix-prefix problem

DOI10.1016/0020-0190(92)90176-VzbMath0748.68021OpenAlexW2063556310WikidataQ126551376 ScholiaQ126551376MaRDI QIDQ1190509

Baruch Schieber, Gad M. Landau, Dan Gusfield

Publication date: 26 September 1992

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(92)90176-v

zbMATH Keywords

string matchingsuffix-prefix match

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Parallel algorithms in computer science (68W10)

Related Items (18)

Faster implementation of a shortest superstring approximation ⋮ Linear-size suffix tries ⋮ An improved algorithm for the all-pairs suffix-prefix problem ⋮ A linear time algorithm for shortest cyclic cover of strings ⋮ Improved length bounds for the shortest superstring problem ⋮ Combinatorial algorithms for DNA sequence assembly ⋮ All-pairs suffix/prefix in optimal time using Aho-Corasick space ⋮ A fast algorithm for the all-pairs suffix-prefix problem ⋮ On updating suffix tree labels ⋮ Recognition of overlap graphs ⋮ 2D Lyndon words and applications ⋮ Optimal prefix and suffix queries on texts ⋮ Unnamed Item ⋮ Efficient algorithms for the all-pairs suffix-prefix problem and the all-pairs substring-prefix problem ⋮ Hierarchical overlap graph ⋮ Superstring Graph: A New Approach for Genome Assembly ⋮ A \(2_3^2\) superstring approximation algorithm ⋮ Distributed suffix trees

Cites Work

• A linear-time algorithm for finding approximate shortest common superstrings
• A greedy approximation algorithm for constructing shortest common superstrings
• Parallel construction of a suffix tree with applications
• Approximation algorithms for the shortest common superstring problem
• A Space-Economical Suffix Tree Construction Algorithm
• Fast Pattern Matching in Strings
• Unnamed Item

This page was built for publication: An efficient algorithm for the all pairs suffix-prefix problem