Linear time algorithms for generalizations of the longest common substring problem

DOI10.1007/S00453-009-9369-1zbMATH Open1219.68126OpenAlexW2050884984MaRDI QIDQ547294FDOQ547294

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

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

zbMATH Keywords

longest common substringsuffix arraysstring mininglongest common repeatrepeat analysis

Mathematics Subject Classification ID

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

Cites Work

• Algorithms on Strings, Trees and Sequences
• Title not available (Why is that?)
• Recursive Star-Tree Parallel Data Structure
• Title not available (Why is that?)
• Fast Pattern Matching in Strings
• Space efficient linear time construction of suffix arrays
• A New Succinct Representation of RMQ-Information and Improvements in the Enhanced Suffix Array
• Title not available (Why is that?)
• Linear-time construction of suffix arrays (extended abstract)
• Linear time algorithm for the longest common repeat problem

Cited In (16)

• Quasi-Linear-Time Algorithm for Longest Common Circular Factor
• A substring-substring LCS data structure
• Longest property-preserved common factor
• Linear time algorithm for the longest common repeat problem
• A simple algorithm for computing the document array
• String Processing and Information Retrieval
• Time-Space Trade-Offs for Longest Common Extensions
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• Computing Longest Common Substrings Via Suffix Arrays
• Longest repeats with a block of \(k\) don't cares
• 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)