An efficient algorithm for the all pairs suffix-prefix problem

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

Baruch Schieber, Gad M. Landau, Dan Gusfield

Publication date: 26 September 1992

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

zbMATH Keywords

string matching; suffix-prefix match

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68W10: Parallel algorithms in computer science

Related Items

Linear-size suffix tries, Recognition of overlap graphs, 2D Lyndon words and applications, Optimal prefix and suffix queries on texts, Efficient algorithms for the all-pairs suffix-prefix problem and the all-pairs substring-prefix problem, On updating suffix tree labels, A \(2_3^2\) superstring approximation algorithm, Faster implementation of a shortest superstring approximation, A fast algorithm for the all-pairs suffix-prefix problem, Combinatorial algorithms for DNA sequence assembly, Distributed suffix trees, An improved algorithm for the all-pairs suffix-prefix problem, A linear time algorithm for shortest cyclic cover of strings, Superstring Graph: A New Approach for Genome Assembly

Cites Work

• Unnamed Item
• 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