2026-07-25T15:15:40Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20641 2024-08-23T05:50:30Z ddc:004 open_access

Approximate Suffix-Prefix Dictionary Queries Zuba, Wiktor Loukides, Grigorios Pissis, Solon P. Thankachan, Sharma V. all-pairs suffix-prefix suffix-prefix queries suffix tree k-errata tree In the all-pairs suffix-prefix (APSP) problem [Gusfield et al., Inf. Process. Lett. 1992], we are given a dictionary R of r strings, S₁,…,S_r, of total length n, and we are asked to find the length SPL_{i,j} of the longest string that is both a suffix of S_i and a prefix of S_j, for all i,j ∈ [1..r]. APSP is a classic problem in string algorithms with applications in bioinformatics, especially in sequence assembly. Since r = |R| is typically very large in real-world applications, considering all r² pairs of strings explicitly is prohibitive. This is when the data structure variant of APSP makes sense; in the same spirit as distance oracles computing shortest paths between any two vertices given online. We show how to quickly locate k-approximate matches (under the Hamming or the edit distance) in R using a version of the k-errata tree [Cole et al., STOC 2004] that we introduce. Let SPL^k_{i,j} be the length of the longest suffix of S_i that is at distance at most k from a prefix of S_j. In particular, for any k = 𝒪(1), we show an 𝒪(nlog^k n)-sized data structure to support the following queries: - One-to-One^k(i,j): output SPL^k_{i,j} in 𝒪(log^k nlog log n) time. - Report^k(i,d): output all j ∈ [1..r], such that SPL^k_{i,j} ≥ d, in 𝒪(log^{k}n(log n/log log n+output)) time, where output denotes the size of the output. In fact, our algorithms work for any value of k not just for k = 𝒪(1), but the formulas bounding the complexities get much more complicated for larger values of k. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Wiktor Zuba and Grigorios Loukides and Solon P. Pissis and Sharma V. Thankachan 2024 Is Part Of LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2024.85 urn:nbn:de:0030-drops-206416 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.85 eng https://creativecommons.org/licenses/by/4.0/legalcode