Linear time algorithms for generalizations of the longest common substring problem

DOI10.1007/S00453-009-9369-1MaRDI QIDQ547294zbMATH OpenOpenAlexFDO

Authors Yong-Cai Geng, Sumit K. Garg

Publication date 1 July 2011

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-009-9369-1

zbMATH Keywords

longest common substringsuffix arraysstring mininglongest common repeatrepeat analysis

Mathematics Subject Classification ID

Combinatorics on words (68R15) Algorithms on strings (68W32)

Recommendations

• String Processing and Information Retrieval
• Linear time algorithm for the longest common repeat problem
• scientific article; zbMATH DE number 1445802
• Computing Longest Common Substrings Via Suffix Arrays
• Time-space trade-offs for the longest common substring problem

Cites work

• scientific article; zbMATH DE number 3913711 (Why is no real title available?)
• scientific article; zbMATH DE number 2038766 (Why is no real title available?)
• scientific article; zbMATH DE number 1786458 (Why is no real title available?)
• A New Succinct Representation of RMQ-Information and Improvements in the Enhanced Suffix Array
• Algorithms on Strings, Trees and Sequences
• Fast Pattern Matching in Strings
• Linear time algorithm for the longest common repeat problem
• Linear-time construction of suffix arrays (extended abstract)
• Recursive Star-Tree Parallel Data Structure
• Space efficient linear time construction of suffix arrays

Cited in

(19)

• Quasi-Linear-Time Algorithm for Longest Common Circular Factor
• A substring-substring LCS data structure
• Linear time algorithm for the longest common repeat problem
• Longest property-preserved common factor
• A simple algorithm for computing the document array
• Longest common subsequence in at least \(k\) length order-isomorphic substrings
• Time-Space Trade-Offs for Longest Common Extensions
• String Processing and Information Retrieval
• scientific article; zbMATH DE number 1445802 (Why is no real title available?)
• Time-space trade-offs for the longest common substring problem
• Longest property-preserved common factor: a new string-processing framework
• The substring inclusion constraint longest common subsequence problem can be solved in quadratic time
• LP-based heuristics for the distinguishing string and substring selection problems
• scientific article; zbMATH DE number 5790350 (Why is no real title available?)
• Computing Longest Common Substrings Via Suffix Arrays
• Longest repeats with a block of \(k\) don't cares
• On longest common property preserved substring queries
• The longest common substring problem
• Inducing enhanced suffix arrays for string collections

This page was built for publication: Linear time algorithms for generalizations of the longest common substring problem

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