Name
Abstract | ||
|---|---|---|
We present two efficient algorithms which, given a compressed representation of a string <em>w</em> of length <em>N</em>, compute the Lyndon factorization of <em>w</em>. Given a straight line program (SLP) <InlineEquation ID=\"IEq1\" <EquationSource Format=\"TEX\"$\\mathcal{S}$</EquationSource> </InlineEquation> of size <em>n</em> and height <em>h</em> that describes <em>w</em>, the first algorithm runs in <em>O</em>(<em>nh</em>(<em>n</em> + log<em>N</em> log<em>n</em>)) time and <em>O</em>(<em>n</em> 2) space. Given the Lempel-Ziv 78 encoding of size <em>s</em> for <em>w</em>, the second algorithm runs in <em>O</em>(<em>s</em> log<em>s</em>) time and space. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1016/j.tcs.2016.03.005 | Theor. Comput. Sci. |
Keywords | Field | DocType |
Lyndon factorization,Straight line program,Lempel-Ziv 78 factorization | Combinatorics,Spacetime,Algorithm,Factorization,Straight-line program,Mathematics,Encoding (memory) | Conference |
Volume | Issue | ISSN |
656 | PB | 0304-3975 |
Citations | PageRank | References |
2 | 0.37 | 13 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Tomohiro I | 1 | 148 | 22.06 |
| Yuto Nakashima | 2 | 57 | 19.52 |
| Shunsuke Inenaga | 3 | 595 | 79.02 |
| Hideo Bannai | 4 | 620 | 79.87 |
| Masayuki Takeda | 5 | 9 | 13.78 |