All-Pairs Suffix-Prefix on Dynamic Set of Strings

Masaru Kikuchi, Shunsuke Inenaga

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish
Title of host publicationString Processing and Information Retrieval - 31st International Symposium, SPIRE 2024, Proceedings
EditorsZsuzsanna Lipták, Edleno Moura, Karina Figueroa, Ricardo Baeza-Yates
PublisherSpringer Science and Business Media Deutschland GmbH
Pages192-203
Number of pages12
ISBN (Print)9783031721991
DOIs
Publication statusPublished - 2025
Event31st International Symposium on String Processing and Information Retrieval, SPIRE 2024 - Puerto Vallarta, Mexico
Duration: Sept 23 2024Sept 25 2024

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume14899 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference31st International Symposium on String Processing and Information Retrieval, SPIRE 2024
Country/TerritoryMexico
CityPuerto Vallarta
Period9/23/249/25/24

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'All-Pairs Suffix-Prefix on Dynamic Set of Strings'. Together they form a unique fingerprint.

Cite this