On 21.01
.2016 as a part of our Foundation for Polish Science Algorithmic Miniworkshop series we will have a seminar by Tomasz Kociumaka. He will give a talk on his recent result on “Optimal Dynamic Strings”. The abstract is given below.
We plan to have a group discussion and joint lunch after his talk.
Abstract:
We study the fundamental problem of maintaining a dynamic collection
of strings under the following operations: concatenate two strings,
split a string into two at a given position, determine the
lexicographical order (smaller, equal, greater) between two strings,
calculate the longest common prefix of two strings. We present a data
structure for this problem, in which updates require only O(log n)
worst-case time with high probability, with n being the total length
of all strings in the collection, and queries take constant worst-case
time. On the lower bound side, we prove that even if the only possible
query is checking equality of two strings, either updates or queries
must take amortized Ω(log n) time; hence our implementation is
optimal. Our data structure can be used as a basic building block to
solve other string problems, such as pattern matching in dynamic
string collections, pattern matching in a history is an edited text,
and processing grammar-compressed strings.
Joint work with Paweł Gawrychowski, Jakub Łącki, Adam Karczmarz, and Piotr Sankowski