Scholarlink

A string w is said to be a minimal unique substring (MUS) of a string T if w occurs exactly once in T, and any proper substring of w occurs at least twice in T. It is known that the number of MUSs in a string T of length n is at most n, and that the set \(\textsf{MUS}(T)\) of all MUSs in T can be computed in O(n) time [Ilie and Smyth, 2011]. Let \(\textsf{MUS}(T,i)\) denote the set of MUSs that contain a position i in a string T. In this short paper, we present matching \(\varTheta (\sqrt{n})\) upper and lower bounds for the number \(|\textsf{MUS}(T,i)|\) of MUSs containing a position i in a string T of length n.

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

On the Number of MUSs Crossing a Position

  • 会议论文

  • 发表日期：

    2026年

查看全文
  • Hiroto Fujimaru,
  • Takuya Mieno,
  • Shunsuke Inenaga

摘要

A string w is said to be a minimal unique substring (MUS) of a string T if w occurs exactly once in T, and any proper substring of w occurs at least twice in T. It is known that the number of MUSs in a string T of length n is at most n, and that the set \(\textsf{MUS}(T)\) of all MUSs in T can be computed in O(n) time [Ilie and Smyth, 2011]. Let \(\textsf{MUS}(T,i)\) denote the set of MUSs that contain a position i in a string T. In this short paper, we present matching \(\varTheta (\sqrt{n})\) upper and lower bounds for the number \(|\textsf{MUS}(T,i)|\) of MUSs containing a position i in a string T of length n.