Finding the longest common nonsuperstring in linear time

DOI10.1016/J.IPL.2009.06.010MaRDI QIDQ989576zbMATH OpenOpenAlexFDO

Authors Joong Chae Na, Dong Kyue Kim, J. S. Sim

Publication date 20 August 2010

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

Full work available at URL https://doi.org/10.1016/j.ipl.2009.06.010

zbMATH Keywords

design of algorithmsgeneralized suffix treelongest common nonsuperstringstring non-inclusion problem

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05)

Recommendations

• String Noninclusion Optimization Problems
• Maximal common subsequences and minimal common supersequences
• Improved Algorithms for Finding Consistent Superstrings Based on a New Graph Model
• String Processing and Information Retrieval
• Linear time algorithm for the longest common repeat problem

Cites work

• A Space-Economical Suffix Tree Construction Algorithm
• Algorithms on Strings, Trees and Sequences
• Data compression via textual substitution
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• On-line construction of suffix trees
• Shortest consistent superstrings computable in polynomial time
• String Noninclusion Optimization Problems
• The Complexity of Some Problems on Subsequences and Supersequences

Cited in

(2)

• A new graph model and algorithms for consistent superstring problems
• String Noninclusion Optimization Problems

This page was built for publication: Finding the longest common nonsuperstring in linear time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q989576)