Parikh Matching in the Streaming Model

Lap-Kei Lee, Moshe Lewenstein, Qin Zhang

Abstract

Let S be a string over an alphabet Σ = {σ 1, σ 2, …}. A Parikh-mapping maps a substring S′ of S to a |Σ|-length vector that contains, in location i of the vector, the count of σ i in S′. Parikh matching refers to the problem of finding all substrings of a text T which match to a given input |Σ|-length count vector.
BibTeX
@inproceedings{lee2012parikh,
  author = {Lap-Kei Lee and Moshe Lewenstein and Qin Zhang},
  title = {{Parikh Matching in the Streaming Model}},
  booktitle = {SPIRE},
  year = {2012},
  doi = {10.1007/978-3-642-34109-0\_35},
}

Loading related content...

Figure