Given two strings 𝑆 and 𝑅, the matching statistics of 𝑆 with respect to 𝑅 is an array of length |𝑆| whose 𝑖th entry encodes the longest prefix of the 𝑖th suffix of 𝑆 that occurs in 𝑅. 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.
Matching statistics—a survey
Lipták, Zsuzsanna;
2026-01-01
Abstract
Given two strings 𝑆 and 𝑅, the matching statistics of 𝑆 with respect to 𝑅 is an array of length |𝑆| whose 𝑖th entry encodes the longest prefix of the 𝑖th suffix of 𝑆 that occurs in 𝑅. 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.
File in questo prodotto:
| File | Dimensione | Formato | |
|---|---|---|---|
|
1-s2.0-S0304397526000551-main.pdf
accesso aperto
Licenza:
Creative commons
Dimensione
2.64 MB
Formato
Adobe PDF
|
2.64 MB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
