## Abstract

Given two strings S and T, each of length at most n, the longest common substring (LCS) problem is to find a longest substring common to S and T. This is a classical problem in computer science with an O(n)-time solution. In the fully dynamic setting, edit operations are allowed in either of the two strings, and the problem is to find an LCS after each edit. We present the first solution to this problem requiring sublinear time in n per edit operation. In particular, we show how to find an LCS after each edit operation in Õ(n^{2/3}) time, after Õ(n)-time and space preprocessing. ^{1} This line of research has been recently initiated in a somewhat restricted dynamic variant by Amir et al. [SPIRE 2017]. More specifically, they presented an Õ(n)-sized data structure that returns an LCS of the two strings after a single edit operation (that is reverted afterwards) in Õ(1) time. At CPM 2018, three papers (Abedin et al., Funakoshi et al., and Urabe et al.) studied analogously restricted dynamic variants of problems on strings. We show that the techniques we develop can be applied to obtain fully dynamic algorithms for all of these variants. The only previously known sublinear-time dynamic algorithms for problems on strings were for maintaining a dynamic collection of strings for comparison queries and for pattern matching, with the most recent advances made by Gawrychowski et al. [SODA 2018] and by Clifford et al. [STACS 2018]. As an intermediate problem we consider computing the solution for a string with a given set of k edits, which leads us, in particular, to answering internal queries on a string. The input to such a query is specified by a substring (or substrings) of a given string. Data structures for answering internal string queries that were proposed by Kociumaka et al. [SODA 2015] and by Gagie et al. [CCCG 2013] are used, along with new ones, based on ingredients such as the suffix tree, heavy-path decomposition, orthogonal range queries, difference covers, and string periodicity.

Original language | English |
---|---|

Title of host publication | 27th Annual European Symposium on Algorithms, ESA 2019 |

Editors | Michael A. Bender, Ola Svensson, Grzegorz Herman |

Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |

ISBN (Electronic) | 9783959771245 |

DOIs | |

Publication status | Published - Sept 2019 |

Externally published | Yes |

Event | 27th Annual European Symposium on Algorithms, ESA 2019 - Munich/Garching, Germany Duration: 9 Sept 2019 → 11 Sept 2019 |

### Publication series

Name | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|

Volume | 144 |

ISSN (Print) | 1868-8969 |

### Conference

Conference | 27th Annual European Symposium on Algorithms, ESA 2019 |
---|---|

Country/Territory | Germany |

City | Munich/Garching |

Period | 9/09/19 → 11/09/19 |

### Funding

Funding Amihood Amir: Supported by Israel Science Foundation (ISF) grant 1475/18 and United States – Israel Binational Science Foundation (BSF) grant 2018141. Panagiotis Charalampopoulos: Partially supported by Israel Science Foundation (ISF) grant 794/13. Jakub Radoszewski: Supported by the “Algorithms for text processing with errors and uncertainties” project carried out within the HOMING programme of the Foundation for Polish Science co-financed by the European Union under the European Regional Development Fund.

Funders | Funder number |
---|---|

United States - Israel Binational Science Foundation | |

European Commission | |

United States-Israel Binational Science Foundation | 2018141, 794/13 |

Fundacja na rzecz Nauki Polskiej | |

Israel Science Foundation | 1475/18 |

European Regional Development Fund |

## Keywords

- Dynamic algorithms
- Longest common substring
- String algorithms