Matching statistics—a survey
Abstract
Given two strings S and R , the matching statistics of S with respect to R is an array of length | S | whose i th entry encodes the longest prefix of the i th suffix of S that occurs in R . Introduced by Chang and Lawler in 1990 for approximate string matching, matching statistics have since found a variety of applications in computational biology, data compression, and string processing. In this article, we survey these applications, as well as the main ideas underlying the different algorithms for efficient construction of the matching statistics that have appeared in the last 30 years.
Fields of Study & Subjects
Algorithms and Data Compression
Machine Learning and Algorithms
Genome Rearrangement Algorithms
Publication details
- Journal / source
- Theoretical Computer Science
- Publisher
- Elsevier BV
- Volume
- 1071
- Pages
- 115796–115796
- Publication date
- 4 February 2026
- Language
- EN