All-Pairs Suffix-Prefix on Fully Dynamic Set of Strings
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915177945890816 |
|---|---|
| author | Kikuchi, Masaru Inenaga, Shunsuke |
| author_facet | Kikuchi, Masaru Inenaga, Shunsuke |
| contents | The all-pairs suffix-prefix (APSP) problem is a classical problem in string processing which has important applications in bioinformatics. Given a set $\mathcal{S} = \{S_1, \ldots, S_k\}$ of $k$ strings, the APSP problem asks one to compute the longest suffix of $S_i$ that is a prefix of $S_j$ for all $k^2$ ordered pairs $\langle S_i, S_j \rangle$ of strings in $\mathcal{S}$. In this paper, we consider the dynamic version of the APSP problem that allows for insertions of new strings to the set of strings. Our objective is, each time a new string $S_i$ arrives to the current set $\mathcal{S}_{i-1} = \{S_1, \ldots, S_{i-1}\}$ of $i-1$ strings, to compute (1) the longest suffix of $S_i$ that is a prefix of $S_j$ and (2) the longest prefix of $S_i$ that is a suffix of $S_j$ for all $1 \leq j \leq i$. We propose an $O(n)$-space data structure which computes (1) and (2) in $O(|S_i| \log σ+ i)$ time for each new given string $S_i$, where $n$ is the total length of the strings. Further, we show how to extend our methods to the fully dynamic version of the APSP problem allowing for both insertions and deletions of strings. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_17814 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | All-Pairs Suffix-Prefix on Fully Dynamic Set of Strings Kikuchi, Masaru Inenaga, Shunsuke Data Structures and Algorithms The all-pairs suffix-prefix (APSP) problem is a classical problem in string processing which has important applications in bioinformatics. Given a set $\mathcal{S} = \{S_1, \ldots, S_k\}$ of $k$ strings, the APSP problem asks one to compute the longest suffix of $S_i$ that is a prefix of $S_j$ for all $k^2$ ordered pairs $\langle S_i, S_j \rangle$ of strings in $\mathcal{S}$. In this paper, we consider the dynamic version of the APSP problem that allows for insertions of new strings to the set of strings. Our objective is, each time a new string $S_i$ arrives to the current set $\mathcal{S}_{i-1} = \{S_1, \ldots, S_{i-1}\}$ of $i-1$ strings, to compute (1) the longest suffix of $S_i$ that is a prefix of $S_j$ and (2) the longest prefix of $S_i$ that is a suffix of $S_j$ for all $1 \leq j \leq i$. We propose an $O(n)$-space data structure which computes (1) and (2) in $O(|S_i| \log σ+ i)$ time for each new given string $S_i$, where $n$ is the total length of the strings. Further, we show how to extend our methods to the fully dynamic version of the APSP problem allowing for both insertions and deletions of strings. |
| title | All-Pairs Suffix-Prefix on Fully Dynamic Set of Strings |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2407.17814 |