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

作者：Amir Amihood; Apostolico Alberto; Hirst Tirza; Landau Gad M; Lewenstein Noa; Rozenberg Liat^*

来源：Theoretical Computer Science, 2016, 656: 146-159.

DOI：10.1016/j.tcs.2016.04.030

• Pattern Matching
• Jumbled Indexing
• Abelian border
• Abelian square
• String algorithms

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 vertical bar Sigma vertical bar 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)vertical bar Sigma vertical bar) in time O (r(2)(logr + vertical bar Sigma vertical bar log vertical bar Sigma vertical bar)), which allows answering histogram queries in O(vertical bar E vertical bar(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 5[1.. j], if such exists. We provide an algorithm that solves this problem in O(vertical bar Sigma vertical bar(r(2) +n)) time, and O(vertical bar Sigma vertical bar n) space. A Jumbled Square is a string of the form x (x) over bar, where (x) over bar 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(vertical bar Sigma vertical bar(r(2) + n)) time, and O(vertical bar Sigma vertical bar n) space.

• 出版日期2016-12-20