Artykuł w czasopiśmie
Brak miniatury
Licencja

CC-BYCC-BY - Uznanie autorstwa

Dynamic longest common substring in polylogarithmic time

Autor
Pokorski, Karol
Gawrychowski, Paweł
Charalampopoulos, Panagiotis
Data publikacji
2020
Abstrakt (EN)

The longest common substring problem consists in finding a longest string that appears as a (contiguous) substring of two input strings. We consider the dynamic variant of this problem, in which we are to maintain two dynamic strings S and T, each of length at most n, that undergo substitutions of letters, in order to be able to return a longest common substring after each substitution. Recently, Amir et al. [ESA 2019] presented a solution for this problem that needs only

Słowa kluczowe EN
string algorithms
dynamic algorithms
longest common substring
Dyscyplina PBN
informatyka
Strony od-do
27:1-27:19
Data udostępnienia w otwartym dostępie
2020-06-29
Licencja otwartego dostępu
Uznanie autorstwa