Matching statistics -- a survey

DOI10.1016/J.TCS.2026.115796MaRDI QIDQ6837846zbMATH OpenFDO

Authors Zsuzsanna Lipták, Francesco Masillo, Simon J. Puglisi

Publication date 26 March 2026

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.TCS.2026.115796

zbMATH Keywords

approximate string matchingdata compressiondata structuresmatching statisticsstring processingsuffix tree

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• r-indexing the eBWT
• A Compressed Enhanced Suffix Array Supporting Fast String Matching
• A faster grammar-based self-index
• A Space-Economical Suffix Tree Construction Algorithm
• A universal algorithm for sequential data compression
• Algorithms on Strings, Trees and Sequences
• An extension of the Burrows-Wheeler transform
• Combined data structure for previous- and next-smaller-values
• Computing suffix links for suffix trees and arrays
• Constructing suffix arrays in linear time
• Fast Algorithms for Finding Nearest Common Ancestors
• Fast parallel and serial approximate string matching
• Fast relative Lempel-Ziv self-index for similar sequences
• Fast string matching with k differences
• Faster entropy-bounded compressed suffix trees
• Fully functional suffix trees and optimal text searching in BWT-runs bounded space
• Genome-Scale Algorithm Design
• scientific article; zbMATH DE number 3913711 (Why is no real title available?)
• scientific article; zbMATH DE number 2079421 (Why is no real title available?)
• scientific article; zbMATH DE number 1512678 (Why is no real title available?)
• scientific article; zbMATH DE number 1555939 (Why is no real title available?)
• scientific article; zbMATH DE number 1786458 (Why is no real title available?)
• scientific article; zbMATH DE number 7700594 (Why is no real title available?)
• Indexing compressed text
• Linear work suffix array construction
• Linear-time suffix sorting -- a new approach for suffix array construction
• Matching statistics speed up BWT construction
• On the Complexity of Finite Sequences
• On-line construction of suffix trees
• Online LZ77 parsing and matching statistics with RLBWTs
• Optimal in-place suffix sorting
• Refining the \(r\)-index
• Relative Lempel-Ziv compression of genomes for large-scale storage and retrieval
• Relative Lempel-Ziv Compression of Suffix Arrays
• Replacing suffix trees with enhanced suffix arrays
• Sequence similarity measures based on bounded Hamming distance
• Space efficient linear time construction of suffix arrays
• Sublinear approximate string matching and biological applications
• Suffix Arrays: A New Method for On-Line String Searches
• Suffix sorting via matching statistics
• Tables
• Two Efficient Algorithms for Linear Time Suffix Array Construction

This page was built for publication: Matching statistics -- a survey

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