Computing the LCP Array of a Labeled Graph
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866911848835579904 |
|---|---|
| author | Alanko, Jarno Cenzato, Davide Cotumaccio, Nicola Kim, Sung-Hwan Manzini, Giovanni Prezza, Nicola |
| author_facet | Alanko, Jarno Cenzato, Davide Cotumaccio, Nicola Kim, Sung-Hwan Manzini, Giovanni Prezza, Nicola |
| contents | The LCP array is an important tool in stringology, allowing to speed up pattern matching algorithms and enabling compact representations of the suffix tree. Recently, Conte et al. [DCC 2023] and Cotumaccio et al. [SPIRE 2023] extended the definition of this array to Wheeler DFAs and, ultimately, to arbitrary labeled graphs, proving that it can be used to efficiently solve matching statistics queries on the graph's paths. In this paper, we provide the first efficient algorithm building the LCP array of a directed labeled graph with $n$ nodes and $m$ edges labeled over an alphabet of size $σ$. After arguing that the natural generalization of a compact-space LCP-construction algorithm by Beller et al. [J. Discrete Algorithms 2013] runs in time $Ω(nσ)$, we present a new algorithm based on dynamic range stabbing building the LCP array in $O(n\log σ)$ time and $O(n\logσ)$ bits of working space. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_14235 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Computing the LCP Array of a Labeled Graph Alanko, Jarno Cenzato, Davide Cotumaccio, Nicola Kim, Sung-Hwan Manzini, Giovanni Prezza, Nicola Data Structures and Algorithms The LCP array is an important tool in stringology, allowing to speed up pattern matching algorithms and enabling compact representations of the suffix tree. Recently, Conte et al. [DCC 2023] and Cotumaccio et al. [SPIRE 2023] extended the definition of this array to Wheeler DFAs and, ultimately, to arbitrary labeled graphs, proving that it can be used to efficiently solve matching statistics queries on the graph's paths. In this paper, we provide the first efficient algorithm building the LCP array of a directed labeled graph with $n$ nodes and $m$ edges labeled over an alphabet of size $σ$. After arguing that the natural generalization of a compact-space LCP-construction algorithm by Beller et al. [J. Discrete Algorithms 2013] runs in time $Ω(nσ)$, we present a new algorithm based on dynamic range stabbing building the LCP array in $O(n\log σ)$ time and $O(n\logσ)$ bits of working space. |
| title | Computing the LCP Array of a Labeled Graph |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2404.14235 |