Matching statistics—a survey

• An extensive and well-integrated survey article on the Matching Statistics, a data structure of interest in string processing, data compression, and genomics. 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.