The Prague Stringology Conference 2008
Satoshi Deguchi, Fumihito Higashijima, Hideo Bannai, Shunsuke Inenaga and Masayuki Takeda
Parameterized Suffix Arrays for Binary Strings
| Abstract: |
| 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. |
| Download paper: |  |
 |
 |
| PostScript | BibTeX reference |
| Download presentation: |  |