Linear time algorithm for the longest common repeat problem

DOI10.1016/J.JDA.2006.03.019MaRDI QIDQ2457296zbMATH OpenOpenAlexFDO

Authors Inbok Lee, Costas S. Iliopoulos, Kunsoo Park

Publication date 30 October 2007

Published in Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jda.2006.03.019

zbMATH Keywords

generalized suffix treerepeatstring algorithm

Mathematics Subject Classification ID

Data structures (68P05) Nonnumerical algorithms (68W05) Analysis of algorithms (68W40)

Recommendations

• String Processing and Information Retrieval
• Linear time algorithms for generalizations of the longest common substring problem
• scientific article; zbMATH DE number 1445802
• scientific article; zbMATH DE number 1782360
• Computing Longest Common Substrings Via Suffix Arrays

Cites work

• A Space-Economical Suffix Tree Construction Algorithm
• Algorithms on Strings, Trees and Sequences
• All Highest Scoring Paths in Weighted Grid Graphs and Their Application to Finding All Approximate Repeats in Strings
• Fast Algorithms for Finding Nearest Common Ancestors
• scientific article; zbMATH DE number 3551946 (Why is no real title available?)
• scientific article; zbMATH DE number 1512678 (Why is no real title available?)
• On Finding Lowest Common Ancestors: Simplification and Parallelization
• On the sorting-complexity of suffix tree construction
• On-line construction of suffix trees

Cited in

(10)

• Longest segment problems
• Longest repeats with a block of \(k\) don't cares
• scientific article; zbMATH DE number 1555948 (Why is no real title available?)
• Alphabet-independent algorithms for finding context-sensitive repeats in linear time
• scientific article; zbMATH DE number 1445802 (Why is no real title available?)
• Quasi-Linear-Time Algorithm for Longest Common Circular Factor
• String Processing and Information Retrieval
• Linear time algorithms for generalizations of the longest common substring problem
• LATIN 2004: Theoretical Informatics
• Finding the longest common nonsuperstring in linear time

This page was built for publication: Linear time algorithm for the longest common repeat problem

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