Wyniki wyszukiwania - BazTech

Ograniczanie wyników

1 Fundamenta Informaticae

1 2018

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: Abelian longest common factor problem

Sortuj według:

Ogranicz wyniki do:

On Abelian Longest Common Factor with and without RLE

Grabowski S., Kociumaka T., Radoszewski J.

Fundamenta Informaticae

2018

Vol. 163, nr 3

225--244

We consider the Abelian longest common factor problem in two scenarios: when input strings are uncompressed and are of length at most n, and when the input strings are run-length encoded and their compressed representations have size at most m. The alphabet size is denoted by σ. For the uncompressed problem, we show an O(n2/ log1+1/σ n)-time and O(n)-space algorithm in the case of σ = O(1), making a non-trivial use of tabulation. For the RLE-compressed problem, we show two algorithms: one working in O(m2σ2 log3m) time and O(m(σ2+log2m)) space, which employs line sweep, and one that works in O(m3) time and O(m) space that applies in a careful way a sliding-window-based approach. The latter improves upon the previously known O(nm2)-time and O(m4)-time algorithms that were recently developed by Sugimoto et al. (IWOCA 2017) and Grabowski (SPIRE 2017), respectively.