Scholarlink

Minimizers sampling is one of the most widely-used mechanisms for sampling strings. Let \(S=S[0]\ldots S[n-1]\) be a string over an alphabet \(\varSigma \) . Further, let \(w\ge 2\) and \(k\ge 1\) be two integers and \(\rho =(\varSigma ^k,\le )\) be a total order on \(\varSigma ^k\) . The minimizer of window \(X=S[i\mathinner {.\,.}i+w+k-2]\) is the smallest position in \([i,i+w-1]\) where the smallest length-k substring of X based on \(\rho \) starts. The set of minimizers for all \(i\in [0,n-w-k+1]\) is the set \(\mathcal {M}_{w,k,\rho }(S)\) of the minimizers of S. The set \(\mathcal {M}_{w,k,\rho }(S)\) can be computed in \(\mathcal {O}(n)\) time. The folklore algorithm computes the minimizer of every window in \(\mathcal {O}(1)\) amortized time using \(\mathcal {O}(w)\) working space. It is thus natural to pose the following two questions: We answer both questions in the affirmative:

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

Minimizers in Semi-dynamic Strings

  • 会议论文

  • 发表日期：

    2026年

查看全文
  • Wiktor Zuba,
  • Oded Lachish,
  • Solon P. Pissis

摘要

Minimizers sampling is one of the most widely-used mechanisms for sampling strings. Let \(S=S[0]\ldots S[n-1]\) be a string over an alphabet \(\varSigma \) . Further, let \(w\ge 2\) and \(k\ge 1\) be two integers and \(\rho =(\varSigma ^k,\le )\) be a total order on \(\varSigma ^k\) . The minimizer of window \(X=S[i\mathinner {.\,.}i+w+k-2]\) is the smallest position in \([i,i+w-1]\) where the smallest length-k substring of X based on \(\rho \) starts. The set of minimizers for all \(i\in [0,n-w-k+1]\) is the set \(\mathcal {M}_{w,k,\rho }(S)\) of the minimizers of S. The set \(\mathcal {M}_{w,k,\rho }(S)\) can be computed in \(\mathcal {O}(n)\) time. The folklore algorithm computes the minimizer of every window in \(\mathcal {O}(1)\) amortized time using \(\mathcal {O}(w)\) working space. It is thus natural to pose the following two questions: We answer both questions in the affirmative: