We present an algorithm that computes the Lempel-Ziv decomposition in $O(n(\logσ+ \log\log n))$ time and $n\logσ+ εn$ bits of space, where $ε$ is a constant rational parameter, $n$ is the length of the input string, and $σ$ is the alphabet size. The $n\logσ$ bits in the space bound are for the input string itself which is treated as read-only.
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。