Computing longest previous factor in linear time and applications

DOI10.1016/J.IPL.2007.10.006zbMATH Open1186.68591OpenAlexW1965743524WikidataQ56767309 ScholiaQ56767309MaRDI QIDQ963336FDOQ963336

Authors: Maxime Crochemore, Lucian Ilie 

Publication date: 19 April 2010

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

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

Recommendations

• Computing the longest previous factor
• Computing longest previous non-overlapping factors
• Efficient algorithms for three variants of the LPF table
• LPF computation revisited
• Efficient Algorithms for Two Extensions of LPF Table: The Power of Suffix Arrays

zbMATH Keywords

analysis of algorithmslongest common prefixstringsdesign of algorithmsrunsrepetitionssuffix arraylongest previous factorLempel-Ziv factorization

Mathematics Subject Classification ID

Analysis of algorithms (68W40)

Cites Work

• Title not available (Why is that?)
• On the Complexity of Finite Sequences
• A universal algorithm for sequential data compression
• Linear-time computation of local periods
• Suffix Arrays: A New Method for On-Line String Searches
• Linear time algorithms for finding and representing all the tandem repeats in a string
• Algorithms on Strings
• Transducers and repetitions
• Space efficient linear time construction of suffix arrays
• Detecting leftmost maximal periodicities
• Fast and Practical Algorithms for Computing All the Runs in a String
• Title not available (Why is that?)
• Replacing suffix trees with enhanced suffix arrays
• Constructing suffix arrays in linear time

Cited In (47)

• Speeding up the detection of tandem repeats over the edit distance
• Counting distinct palindromes in a word in linear time
• Quasi-Linear-Time Algorithm for Longest Common Circular Factor
• The ``runs conjecture
• Reversing longest previous factor tables is hard
• Space-efficient representation of truncated suffix trees, with applications to Markov order estimation
• On parsing optimality for dictionary-based text compression -- the \texttt{Zip} case
• Efficient algorithms for three variants of the LPF table
• Parameterized longest previous factor
• Faster online computation of the succinct longest previous factor array
• Dictionary-symbolwise flexible parsing
• String inference from longest-common-prefix array
• Variations of the parameterized longest previous factor
• Title not available (Why is that?)
• Computing regularities in strings: a survey
• LZ77 computation based on the run-length encoded BWT
• LPF computation revisited
• Factorizing strings into repetitions
• Parameterized longest previous factor
• Algorithms and combinatorial properties on shortest unique palindromic substrings
• The three squares lemma revisited
• LZRR: LZ77 parsing with right reference
• Repetitions in strings: algorithms and combinatorics
• Note on the greedy parsing optimality for dictionary-based text compression
• Longest previous overlapping factor array
• Using static suffix array in dynamic application: case of text compression by longest first substitution
• Title not available (Why is that?)
• Computing the longest previous factor
• Efficient on-line repetition detection
• Almost linear time computation of maximal repetitions in run length encoded strings
• An Online Algorithm for Finding the Longest Previous Factors
• Computing longest previous non-overlapping factors
• The ``runs theorem
• A brief history of parameterized matching problems
• Verifying and enumerating parameterized border arrays
• Locating maximal approximate runs in a string
• Generalized substring compression
• Lempel-Ziv Factorization Revisited
• Towards a Solution to the “Runs” Conjecture
• A prefix array for parameterized strings
• Phenomenology of coupled nonlinear oscillators
• List Factoring and Relative Worst Order Analysis
• Direct linear time construction of parameterized suffix and LCP arrays for constant alphabets
• On the computation of longest previous non-overlapping factors
• Optimally computing compressed indexing arrays based on the compact directed acyclic word graph
• Sublinear time Lempel-Ziv (LZ77) factorization
• Lazy Lempel-Ziv factorization algorithms

This page was built for publication: Computing longest previous factor in linear time and applications

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