A palindrome is a string that reads the same forward and backward. A palindromic substring $w$ of a string $T$ is called a minimal unique palindromic substring (MUPS) of $T$ if $w$ occurs only once in $T$ and any proper palindromic substring of $w$ occurs at least twice in $T$. MUPSs are utilized for answering the shortest unique palindromic substring problem, which is motivated by molecular biology [Inoue et al., 2018]. Given a string $T$ of length $n$, all MUPSs of $T$ can be computed in $O(n)$ time. In this paper, we study the problem of updating the set of MUPSs when a character in the input string $T$ is substituted by another character. We first analyze the number $d$ of changes of MUPSs when a character is substituted, and show that $d$ is in $O(\log n)$. Further, we present an algorithm that uses $O(n)$ time and space for preprocessing, and updates the set of MUPSs in $O(\log\sigma + (\log\log n)^2 + d)$ time where $\sigma$ is the alphabet size. We also propose a variant of the algorithm, which runs in optimal $O(1+d)$ time when the alphabet size is constant.


翻译:等离子线是一个字符串, 读出相同的前向和后向。 等离子线是一个字符串。 等离子线以一字符串为单位, 以美元为单位, 如果美元仅发生一次, 而任何适当的低离子字符串以美元为单位, 则至少发生两倍于美元。 MUPS 用于应对由分子生物学[ Inoue 和 Al., 2018] 驱动的最短独特的低离子字符串问题。 由于字符串以美元为单位, 所有T$的MUPS, 都被称为最低特异的低离子串( MUPS) 美元。 在本文中, 当输入字符串中的一个字符以美元换成美元为单位时, 我们研究如何更新 MUPS 的数据集, 当我们用美元为单位时, 我们用美元 的平差值为n= 的平差值 。

0
下载
关闭预览

相关内容

专知会员服务
50+阅读 · 2020年12月14日
【Google】梯度下降,48页ppt
专知会员服务
80+阅读 · 2020年12月5日
最新《Transformers模型》教程,64页ppt
专知会员服务
306+阅读 · 2020年11月26日
Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
109+阅读 · 2020年5月15日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
已删除
将门创投
4+阅读 · 2020年1月6日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
【LeetCode 500】关关的刷题日记27 Keyboard Row
专知
3+阅读 · 2017年11月5日
VIP会员
相关资讯
已删除
将门创投
4+阅读 · 2020年1月6日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
【LeetCode 500】关关的刷题日记27 Keyboard Row
专知
3+阅读 · 2017年11月5日
Top
微信扫码咨询专知VIP会员