.png){kind=icon}
返回
Internal quasiperiod queries
.png){kind=icon}
PRE
AI
DOI：10.1016/j.tcs.2026.115747.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
内部模式匹配要求回答关于给定字符串的因子的查询。许多关于回答内部周期查询的结果已知，这些查询要求给出给定因子的周期。在本文中，我们研究了要求给出给定因子的覆盖（也称为准周期）的内部查询。设n表示字符串的长度，m表示所讨论的因子的长度。我们提出了一种数据结构，该结构在预处理后，能够在O(logm)时间内回答最短覆盖的查询，并在O(log m log log m)时间内给出所有覆盖的表示，预处理时间和空间复杂度为O(n log n)。这是SPIRE 2020会议论文的完整版本，查询复杂度通过log log n因子得到改进，并增加了应用。
Keyword:
Cover of a string
Internal pattern matching
Seed of a string
期刊
IF:
1
论文数:
248
被引数:
1.0W
机构
引用论文
.png){kind=icon}
A correction to “An optimal algorithm to compute all the covers of a string”对“计算字符串所有覆盖的最优算法”的更正
PREAI
分享收藏分享收藏
查看更多内容