License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CPM.2018.11
URN: urn:nbn:de:0030-drops-86983
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8698/
Amir, Amihood ;
Boneh, Itai
Locally Maximal Common Factors as a Tool for Efficient Dynamic String Algorithms
Abstract
There has been recent interest in dynamic string algorithms, i.e. string problems where the input changes dynamically. One such problem is the longest common factor (LCF) problem. It is well known that the LCF of two strings S and D of length n over a fixed constant-sized alphabet Sigma can be computed in time linear in n. Recently, a new challenge was introduced - finding the LCF of two strings in a dynamic setting. The problem is the fully dynamic one sided LCF (FDOS-LCF) problem. In the FDOS-LCF problem we get q consecutive queries of the form <i,alpha >, where each such query means: "replace D[i] by alpha, alpha in Sigma and output the LCF of S and (the updated) D. The goal is to initially preprocess S and D so that we do not need O(n) time to compute an LCF for each such query.
The state-of-the-art is an algorithm that preprocesses the two strings S and D in time O(n log^4 n). Subsequently, the algorithm answers in time O(log^3 n) a single query of the form: Given a position i on D and a letter alpha, return an LCF of S and D', where D' is the string resulting from D after substituting D[i] with alpha. That algorithm is not extendable to multiple queries. In this paper we present a tool - Locally Maximal Common Factors (LMCF) - that proves to be quite useful in solving some restricted versions of the FDOS-LCF problem . The versions we solve are the Decremental FDOS-LCS problem, where every change <i,alpha> is of the form <i,omega>, omega !in Sigma, and the Periodic FDOS-LCS problem, where S is a periodic string with period length p.
For the decremental problem we provide an algorithm with linear time preprocessing and O(log log n) time per query. For the periodic problem our preprocessing time is linear and the query time is O(p log log n).
BibTeX - Entry
@InProceedings{amir_et_al:LIPIcs:2018:8698,
author = {Amihood Amir and Itai Boneh},
title = {{Locally Maximal Common Factors as a Tool for Efficient Dynamic String Algorithms}},
booktitle = {Annual Symposium on Combinatorial Pattern Matching (CPM 2018)},
pages = {11:1--11:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-074-3},
ISSN = {1868-8969},
year = {2018},
volume = {105},
editor = {Gonzalo Navarro and David Sankoff and Binhai Zhu},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2018/8698},
URN = {urn:nbn:de:0030-drops-86983},
doi = {10.4230/LIPIcs.CPM.2018.11},
annote = {Keywords: Dynamic Algorithms, Periodicity, Longest Common Factor, Priority Queue Data Structures, Suffix
Tree, Balanced Search Tree, Range Maximum Queries}
}
|
Keywords: |
|
Dynamic Algorithms, Periodicity, Longest Common Factor, Priority Queue Data Structures, Suffix
Tree, Balanced Search Tree, Range Maximum Queries |
|
Collection: |
|
Annual Symposium on Combinatorial Pattern Matching (CPM 2018) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
18.05.2018 |
