All-pairs suffix/prefix in optimal time using Aho-Corasick space

Grigorios Loukides; Solon P. Pissis

doi:10.1016/j.ipl.2022.106275

All-pairs suffix/prefix in optimal time using Aho-Corasick space

Grigorios Loukides, Solon P. Pissis^*

^*Corresponding author for this work

Research output: Contribution to Journal › Article › Academic › peer-review

Abstract

The all-pairs suffix/prefix (APSP) problem is a classic problem in computer science with many applications in bioinformatics. Given a set {S₁,…,S_k} of k strings of total length n, we are asked to find, for each string S_i, i∈[1,k], its longest suffix that is a prefix of string S_j, for all j≠i, j∈[1,k]. Several algorithms running in the optimal O(n+k²) time for solving APSP are known. All of these algorithms are based on suffix sorting and thus require space Ω(n) in any case. We consider the parameterized version of the APSP problem, denoted by ℓ-APSP, in which we are asked to output only the pairs whose suffix/prefix overlap is of length at least ℓ. We give an algorithm for solving ℓ-APSP that runs in the optimal O(n+|OUTPUT_ℓ|) time using O(n) space, where OUTPUT_ℓ is the set of output pairs. Our algorithm is thus optimal for the APSP problem as well by setting ℓ=0. Notably, our algorithm is fundamentally different from all optimal algorithms solving the APSP problem: it does not rely on sorting the suffixes of all input strings but on a novel traversal of the Aho-Corasick machine, and it thus requires space linear in the size of the machine.

Original language	English
Article number	106275
Pages (from-to)	1-6
Number of pages	6
Journal	Information Processing Letters
Volume	178
Early online date	28 Apr 2022
DOIs	https://doi.org/10.1016/j.ipl.2022.106275
Publication status	Published - Nov 2022

Bibliographical note

Funding Information:
The authors would like to thank Anne Luesink (Vrije Universiteit) for implementing the algorithm underlying Theorem 1 . The source code is freely available at https://github.com/ALuesink/APSP_algorithm . Grigorios Loukides is partially supported by the Leverhulme Trust RPG-2019-399 project. Solon P. Pissis is partially supported by the PANGAIA and ALPACA projects that have received funding from the European Union's Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreements No 872539 and 956229 , respectively.

Publisher Copyright:
© 2022 The Authors

Funding

The authors would like to thank Anne Luesink (Vrije Universiteit) for implementing the algorithm underlying Theorem 1 . The source code is freely available at https://github.com/ALuesink/APSP_algorithm . Grigorios Loukides is partially supported by the Leverhulme Trust RPG-2019-399 project. Solon P. Pissis is partially supported by the PANGAIA and ALPACA projects that have received funding from the European Union's Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreements No 872539 and 956229 , respectively.

Funders	Funder number
ALPACA
PANGAIA
Horizon 2020 Framework Programme
H2020 Marie Skłodowska-Curie Actions	872539, 956229
Leverhulme Trust	RPG-2019-399
Horizon 2020

Keywords

Aho-Corasick machine
Algorithms
Data structures
Failure transition tree
String algorithms

Access to Document

10.1016/j.ipl.2022.106275

Persistent URL (handle)

Persistent link

Cite this

@article{dd30b01ba0c14fc18716aee606dafd8e,

title = "All-pairs suffix/prefix in optimal time using Aho-Corasick space",

abstract = "The all-pairs suffix/prefix (APSP) problem is a classic problem in computer science with many applications in bioinformatics. Given a set {S1,…,Sk} of k strings of total length n, we are asked to find, for each string Si, i∈[1,k], its longest suffix that is a prefix of string Sj, for all j≠i, j∈[1,k]. Several algorithms running in the optimal O(n+k2) time for solving APSP are known. All of these algorithms are based on suffix sorting and thus require space Ω(n) in any case. We consider the parameterized version of the APSP problem, denoted by ℓ-APSP, in which we are asked to output only the pairs whose suffix/prefix overlap is of length at least ℓ. We give an algorithm for solving ℓ-APSP that runs in the optimal O(n+|OUTPUTℓ|) time using O(n) space, where OUTPUTℓ is the set of output pairs. Our algorithm is thus optimal for the APSP problem as well by setting ℓ=0. Notably, our algorithm is fundamentally different from all optimal algorithms solving the APSP problem: it does not rely on sorting the suffixes of all input strings but on a novel traversal of the Aho-Corasick machine, and it thus requires space linear in the size of the machine.",

keywords = "Aho-Corasick machine, Algorithms, Data structures, Failure transition tree, String algorithms",

author = "Grigorios Loukides and Pissis, {Solon P.}",

note = "Funding Information: The authors would like to thank Anne Luesink (Vrije Universiteit) for implementing the algorithm underlying Theorem 1 . The source code is freely available at https://github.com/ALuesink/APSP_algorithm . Grigorios Loukides is partially supported by the Leverhulme Trust RPG-2019-399 project. Solon P. Pissis is partially supported by the PANGAIA and ALPACA projects that have received funding from the European Union's Horizon 2020 research and innovation programme under the Marie Sk{\l}odowska-Curie grant agreements No 872539 and 956229 , respectively. Publisher Copyright: {\textcopyright} 2022 The Authors",

year = "2022",

month = nov,

doi = "10.1016/j.ipl.2022.106275",

language = "English",

volume = "178",

pages = "1--6",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier",

}

TY - JOUR

T1 - All-pairs suffix/prefix in optimal time using Aho-Corasick space

AU - Loukides, Grigorios

AU - Pissis, Solon P.

N1 - Funding Information: The authors would like to thank Anne Luesink (Vrije Universiteit) for implementing the algorithm underlying Theorem 1 . The source code is freely available at https://github.com/ALuesink/APSP_algorithm . Grigorios Loukides is partially supported by the Leverhulme Trust RPG-2019-399 project. Solon P. Pissis is partially supported by the PANGAIA and ALPACA projects that have received funding from the European Union's Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreements No 872539 and 956229 , respectively. Publisher Copyright: © 2022 The Authors

PY - 2022/11

Y1 - 2022/11

N2 - The all-pairs suffix/prefix (APSP) problem is a classic problem in computer science with many applications in bioinformatics. Given a set {S1,…,Sk} of k strings of total length n, we are asked to find, for each string Si, i∈[1,k], its longest suffix that is a prefix of string Sj, for all j≠i, j∈[1,k]. Several algorithms running in the optimal O(n+k2) time for solving APSP are known. All of these algorithms are based on suffix sorting and thus require space Ω(n) in any case. We consider the parameterized version of the APSP problem, denoted by ℓ-APSP, in which we are asked to output only the pairs whose suffix/prefix overlap is of length at least ℓ. We give an algorithm for solving ℓ-APSP that runs in the optimal O(n+|OUTPUTℓ|) time using O(n) space, where OUTPUTℓ is the set of output pairs. Our algorithm is thus optimal for the APSP problem as well by setting ℓ=0. Notably, our algorithm is fundamentally different from all optimal algorithms solving the APSP problem: it does not rely on sorting the suffixes of all input strings but on a novel traversal of the Aho-Corasick machine, and it thus requires space linear in the size of the machine.

AB - The all-pairs suffix/prefix (APSP) problem is a classic problem in computer science with many applications in bioinformatics. Given a set {S1,…,Sk} of k strings of total length n, we are asked to find, for each string Si, i∈[1,k], its longest suffix that is a prefix of string Sj, for all j≠i, j∈[1,k]. Several algorithms running in the optimal O(n+k2) time for solving APSP are known. All of these algorithms are based on suffix sorting and thus require space Ω(n) in any case. We consider the parameterized version of the APSP problem, denoted by ℓ-APSP, in which we are asked to output only the pairs whose suffix/prefix overlap is of length at least ℓ. We give an algorithm for solving ℓ-APSP that runs in the optimal O(n+|OUTPUTℓ|) time using O(n) space, where OUTPUTℓ is the set of output pairs. Our algorithm is thus optimal for the APSP problem as well by setting ℓ=0. Notably, our algorithm is fundamentally different from all optimal algorithms solving the APSP problem: it does not rely on sorting the suffixes of all input strings but on a novel traversal of the Aho-Corasick machine, and it thus requires space linear in the size of the machine.

KW - Aho-Corasick machine

KW - Algorithms

KW - Data structures

KW - Failure transition tree

KW - String algorithms

UR - http://www.scopus.com/inward/record.url?scp=85129975164&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85129975164&partnerID=8YFLogxK

U2 - 10.1016/j.ipl.2022.106275

DO - 10.1016/j.ipl.2022.106275

M3 - Article

AN - SCOPUS:85129975164

SN - 0020-0190

VL - 178

SP - 1

EP - 6

JO - Information Processing Letters

JF - Information Processing Letters

M1 - 106275

ER -

All-pairs suffix/prefix in optimal time using Aho-Corasick space

Abstract

Bibliographical note

Funding

Keywords

Access to Document

Persistent URL (handle)

Other files and links

Fingerprint

Cite this