Parameterized suffix arrays for binary strings

Satoshi Deguchi, Fumihito Higashijima, Hideo Bannai, Shunsuke Inenaga, Masayuki Takeda

Research output: Chapter in Book/Report/Conference proceedingConference contribution

28 Citations (Scopus)


We consider the suffix array for parameterized binary strings that consist of only two types of parameter symbols. We show that the parameterized suffix array, as well as its longest common prefix (LCP) array of such strings can be constructed in linear time. The construction is direct, in that it does not require the construction of a parameterized suffix tree. Although parameterized pattern matching of binary strings can be done by either searching for a pattern and its inverse on a standard suffix array, or constructing two independent standard suffix arrays for the text and its inverse, our approach only needs a single p-suffix array and a single search.

Original languageEnglish
Title of host publicationProceedings of the Prague Stringology Conference 2008
Number of pages11
Publication statusPublished - 2008
EventPrague Stringology Conference 2008, PSC 2008 - Prague, Czech Republic
Duration: Sept 1 2008Sept 3 2008

Publication series

NameProceedings of the Prague Stringology Conference 2008


OtherPrague Stringology Conference 2008, PSC 2008
Country/TerritoryCzech Republic

All Science Journal Classification (ASJC) codes

  • General Mathematics


Dive into the research topics of 'Parameterized suffix arrays for binary strings'. Together they form a unique fingerprint.

Cite this