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 constantsized 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 (FDOSLCF) problem. In the FDOSLCF 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 stateoftheart 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 FDOSLCF problem . The versions we solve are the Decremental FDOSLCS problem, where every change <i,alpha> is of the form <i,omega>, omega !in Sigma, and the Periodic FDOSLCS 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:111:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770743},
ISSN = {18688969},
year = {2018},
volume = {105},
editor = {Gonzalo Navarro and David Sankoff and Binhai Zhu},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2018/8698},
URN = {urn:nbn:de:0030drops86983},
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 