Scholarlink

We tackle the problems of computing the rightmost variant of the Lempel-Ziv factorizations in the online/sliding model. Previous best bounds for this problem are \(O(n \log n)\)  time with O(n) space, due to Amir et al. [IPL 2002] for the online model, and due to Larsson [CPM 2014] for the sliding model. In this paper, we present faster \(O(n \log n / \log \log n)\) -time solutions to both of the online/sliding models. Our algorithms are built on a simple data structure named BP-linked trees, and on a slightly improved version of the range minimum/maximum query (RmQ/RMQ) data structure on a dynamic list of integers. We also present other applications of our algorithms.

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Faster and Simpler Online/Sliding Rightmost Lempel-Ziv Factorizations

  • 会议论文

  • 发表日期：

    2025年

查看全文
  • Wataru Sumiyoshi,
  • Takuya Mieno,
  • Shunsuke Inenaga

摘要

We tackle the problems of computing the rightmost variant of the Lempel-Ziv factorizations in the online/sliding model. Previous best bounds for this problem are \(O(n \log n)\)  time with O(n) space, due to Amir et al. [IPL 2002] for the online model, and due to Larsson [CPM 2014] for the sliding model. In this paper, we present faster \(O(n \log n / \log \log n)\) -time solutions to both of the online/sliding models. Our algorithms are built on a simple data structure named BP-linked trees, and on a slightly improved version of the range minimum/maximum query (RmQ/RMQ) data structure on a dynamic list of integers. We also present other applications of our algorithms.