TY - CHAP

T1 - Longest Common Factor After One Edit Operation

AU - Amir, Amihood

AU - Charalampopoulos, Panagiotis

AU - Iliopoulos, Costas S.

AU - Pissis, Solon P.

AU - Radoszewski, Jakub

PY - 2017/9/6

Y1 - 2017/9/6

N2 - It is well known that the longest common factor (LCF) of two strings over an integer alphabet can be computed in time linear in the total length of the two strings. Our aim here is to present an algorithm that preprocesses two strings S and T in order to answer the following type of queries: Given a position i on S and a letter αα, return an LCF of T and S′S′, where S′S′ is the string resulting from S after substituting S[i] with αα. In what follows, we present an algorithm that, given two strings of length at most n, constructs in O(nlog4n)O(nlog4n) expected time a data structure of O(nlog3n)O(nlog3n) space that answers such queries in O(log3n)O(log3n) time per query. After some trivial modifications, our approach can also support the case of single letter insertions or deletions in S.

AB - It is well known that the longest common factor (LCF) of two strings over an integer alphabet can be computed in time linear in the total length of the two strings. Our aim here is to present an algorithm that preprocesses two strings S and T in order to answer the following type of queries: Given a position i on S and a letter αα, return an LCF of T and S′S′, where S′S′ is the string resulting from S after substituting S[i] with αα. In what follows, we present an algorithm that, given two strings of length at most n, constructs in O(nlog4n)O(nlog4n) expected time a data structure of O(nlog3n)O(nlog3n) space that answers such queries in O(log3n)O(log3n) time per query. After some trivial modifications, our approach can also support the case of single letter insertions or deletions in S.

U2 - 10.1007/978-3-319-67428-5_2

DO - 10.1007/978-3-319-67428-5_2

M3 - Other chapter contribution

SN - 978-3-319-67427-8

VL - 10508

T3 - Lecture Notes in Computer Science

SP - 14

EP - 26

BT - String Processing and Information Retrieval: 24th International Symposium, SPIRE 2017, Palermo, Italy, September 26--29, 2017, Proceedings

A2 - Fici, Gabriele

A2 - Sciortino, Marinella

A2 - Venturini, Rossano

PB - Springer International Publishing Switzerland

CY - Cham

T2 - 24th International Symposium, SPIRE 2017 Palermo, Italy, September 26–29, 2017

Y2 - 26 September 2017 through 29 September 2017

ER -