The Binary Jumbled String Matching Problem is defined as follows: Given a string s over {a,b} of length n and a query (x,y), with x,y non-negative integers, decide whether s has a substring t with exactly x aÊs and y bÊs. Previous solutions created an index of size O(n) in a pre-processing step, which was then used to answer queries in constant time. The fastest algorithms for construction of this index have running time O( n2/logn) (Burcsi et al., 2010 [1]; Moosa and Rahman, 2010 [7]), or O(n2/log2n) in the word-RAM model (Moosa and Rahman, 2012 [8]). We propose an index constructed directly from the run-length encoding of s. The construction time of our index is O(n+ρ2logρ), where O(n) is the time for computing the run-length encoding of s and ρ is the length of this encoding - this is no worse than previous solutions if ρ=O(n/logn) and better if ρ=o(n/logn). Our index L can be queried in O(logρ) time. While |L|=O(min(n,ρ2)) in the worst case, preliminary investigations have indicated that |L| may often be close to ρ. Furthermore, the algorithm for constructing the index is conceptually simple and easy to implement. In an attempt to shed light on the structure and size of our index, we characterize it in terms of the prefix normal forms of s introduced in Fici and Lipták (2011) [6].

Binary jumbled string matching for highly run-length compressible texts

Liptak, Zsuzsanna
2013

Abstract

The Binary Jumbled String Matching Problem is defined as follows: Given a string s over {a,b} of length n and a query (x,y), with x,y non-negative integers, decide whether s has a substring t with exactly x aÊs and y bÊs. Previous solutions created an index of size O(n) in a pre-processing step, which was then used to answer queries in constant time. The fastest algorithms for construction of this index have running time O( n2/logn) (Burcsi et al., 2010 [1]; Moosa and Rahman, 2010 [7]), or O(n2/log2n) in the word-RAM model (Moosa and Rahman, 2012 [8]). We propose an index constructed directly from the run-length encoding of s. The construction time of our index is O(n+ρ2logρ), where O(n) is the time for computing the run-length encoding of s and ρ is the length of this encoding - this is no worse than previous solutions if ρ=O(n/logn) and better if ρ=o(n/logn). Our index L can be queried in O(logρ) time. While |L|=O(min(n,ρ2)) in the worst case, preliminary investigations have indicated that |L| may often be close to ρ. Furthermore, the algorithm for constructing the index is conceptually simple and easy to implement. In an attempt to shed light on the structure and size of our index, we characterize it in terms of the prefix normal forms of s introduced in Fici and Lipták (2011) [6].
String algorithms; jumbled pattern matching; prefix normal form; data structures
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11562/614552
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 21
  • ???jsp.display-item.citation.isi??? 16
social impact