Name
Title | ||
|---|---|---|
Direct Linear Time Construction of Parameterized Suffix and LCP Arrays for Constant Alphabets. |
Abstract | ||
|---|---|---|
We present the first worst-case linear time algorithm that directly computes the parameterized suffix and LCP arrays for constant sized alphabets. Previous algorithms either required quadratic time or the parameterized suffix tree to be built first. More formally, for a string over static alphabet $\Sigma$ and parameterized alphabet $\Pi$, our algorithm runs in $O(n\pi)$ time and $O(n)$ words of space, where $\pi$ is the number of distinct symbols of $\Pi$ in the string. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1007/978-3-030-32686-9_27 | SPIRE |
Field | DocType | Volume |
Discrete mathematics,Parameterized complexity,Combinatorics,Suffix,Suffix tree,Time complexity,Mathematics,Alphabet | Journal | abs/1906.00563 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Noriki Fujisato | 1 | 0 | 0.34 |
| Yuto Nakashima | 2 | 57 | 19.52 |
| Shunsuke Inenaga | 3 | 595 | 79.02 |
| Hideo Bannai | 4 | 620 | 79.87 |
| Masayuki Takeda | 5 | 9 | 13.78 |