TY - GEN
T1 - All-Pairs Suffix-Prefix on Dynamic Set of Strings
AU - Kikuchi, Masaru
AU - Inenaga, Shunsuke
N1 - Publisher Copyright:
© The Author(s), under exclusive license to Springer Nature Switzerland AG 2025.
PY - 2025
Y1 - 2025
N2 - The all-pairs suffix-prefix (APSP) problem is a classical problem in string processing which has important applications in bioinformatics. Given a set S={S1,…,Sk} of k strings, the APSP problem asks one to compute the longest suffix of Si that is a prefix of Sj for all k2 ordered pairs ⟨Si,Sj⟩ of strings in 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 Si arrives to the current set Si-1={S1,…,Si-1} of i-1 strings, to compute (1) the longest suffix of Si that is a prefix of Sj and (2) the longest prefix of Si that is a suffix of Sj for all 1≤j≤i. We propose an O(n)-space data structure which computes (1) and (2) in O(|Si|logσ+i) time for each new given string Si, where n is the total length of the strings.
AB - The all-pairs suffix-prefix (APSP) problem is a classical problem in string processing which has important applications in bioinformatics. Given a set S={S1,…,Sk} of k strings, the APSP problem asks one to compute the longest suffix of Si that is a prefix of Sj for all k2 ordered pairs ⟨Si,Sj⟩ of strings in 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 Si arrives to the current set Si-1={S1,…,Si-1} of i-1 strings, to compute (1) the longest suffix of Si that is a prefix of Sj and (2) the longest prefix of Si that is a suffix of Sj for all 1≤j≤i. We propose an O(n)-space data structure which computes (1) and (2) in O(|Si|logσ+i) time for each new given string Si, where n is the total length of the strings.
KW - Aho-Corasick automata
KW - all-pairs suffix-prefix problem
KW - directed acyclic word graphs (DAWGs)
UR - http://www.scopus.com/inward/record.url?scp=85205372372&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85205372372&partnerID=8YFLogxK
U2 - 10.1007/978-3-031-72200-4_15
DO - 10.1007/978-3-031-72200-4_15
M3 - Conference contribution
AN - SCOPUS:85205372372
SN - 9783031721991
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 192
EP - 203
BT - String Processing and Information Retrieval - 31st International Symposium, SPIRE 2024, Proceedings
A2 - Lipták, Zsuzsanna
A2 - Moura, Edleno
A2 - Figueroa, Karina
A2 - Baeza-Yates, Ricardo
PB - Springer Science and Business Media Deutschland GmbH
T2 - 31st International Symposium on String Processing and Information Retrieval, SPIRE 2024
Y2 - 23 September 2024 through 25 September 2024
ER -