Algorithms for Jumbled Indexing, Jumbled Border and Jumbled Square on run-length encoded strings

Autor: Gad M. Landau, Amihood Amir, Noa Lewenstein, Tirza Hirst, Liat Rozenberg, Alberto Apostolico
Rok vydání: 2016
Předmět:
Zdroj: Theoretical Computer Science. 656:146-159
ISSN: 0304-3975
DOI: 10.1016/j.tcs.2016.04.030
Popis: In this paper we investigate jumbled (Abelian) versions of three classical strings problems. In all these problems we assume the input string S 1 . . n is given in its run-length format S ' 1 . . r .The Jumbled Indexing problem is the problem of indexing a string S ' 1 . . r over | Σ | for histogram queries, i.e. given a pattern P, we want to find all substrings of S that are permutations of P. We provide an algorithm that constructs an index of size O ( r 2 | Σ | ) in time O ( r 2 ( log ź r + | Σ | log ź | Σ | ) ) , which allows answering histogram queries in O ( | Σ | 3 log ź r ) -time.The Jumbled Border problem is the problem of finding for every location j in S, the longest proper prefix of S 1 . . j that is also a permutation of a proper suffix of S 1 . . j , if such exists. We provide an algorithm that solves this problem in O ( | Σ | ( r 2 + n ) ) time, and O ( | Σ | n ) space.A Jumbled Square is a string of the form x x ź , where x ź is a permutation of x. The Jumbled Square problem is the problem of finding for every location j in S, the longest jumbled square that ends in j, if such exists. We provide an algorithm that solves this problem in O ( | Σ | ( r 2 + n ) ) time, and O ( | Σ | n ) space.
Databáze: OpenAIRE
Externí odkaz: