King's College London

Research portal

Longest Common Factor After One Edit Operation

Research output: Chapter in Book/Report/Conference proceedingOther chapter contribution

Original languageEnglish
Title of host publicationString Processing and Information Retrieval: 24th International Symposium, SPIRE 2017, Palermo, Italy, September 26--29, 2017, Proceedings
EditorsGabriele Fici, Marinella Sciortino, Rossano Venturini
Place of PublicationCham
PublisherSpringer International Publishing Switzerland
Pages14-26
Number of pages13
Volume10508
ISBN (Electronic)978-3-319-67428-5
ISBN (Print)978-3-319-67427-8
DOIs
Publication statusE-pub ahead of print - 6 Sep 2017
Event24th International Symposium, SPIRE 2017 Palermo, Italy, September 26–29, 2017 -
Duration: 26 Sep 201729 Sep 2017

Publication series

NameLecture Notes in Computer Science
PublisherSpringer International Publishing
Name
Number0302-9743

Conference

Conference24th International Symposium, SPIRE 2017 Palermo, Italy, September 26–29, 2017
Period26/09/201729/09/2017

King's Authors

Abstract

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(nlog4⁡n) expected time a data structure of O(nlog3n)O(nlog3⁡n) space that answers such queries in O(log3n)O(log3⁡n) time per query. After some trivial modifications, our approach can also support the case of single letter insertions or deletions in S.

View graph of relations

© 2018 King's College London | Strand | London WC2R 2LS | England | United Kingdom | Tel +44 (0)20 7836 5454