.png){kind=icon}
返回
A textbook solution for dynamic strings
.png){kind=icon}
OA
AI
DOI：10.1016/j.tcs.2026.115746.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
我们考虑在维护字符串集合的同时高效支持它们的分割、连接以及比较两个子串，并计算两个后缀之间的最长公共前缀的问题。该问题可以在更新时以最优时间 O(log N) whp 解决，查询时以最坏情况时间 O(1) 解决，其中 N 是集合的总大小 [Gawrychowski et al., SODA 2018]。我们在此提出一种基于增强伸展树森林（FeST）的更简单解决方案，其中更新和子串比较均以 O(log n) 均摊时间完成，n 是操作中涉及的字符串长度之和。最长公共前缀的长度 8 以 O(log n + log2 8) 均摊时间计算。我们的查询结果以高概率正确。我们的更简单解决方案能够在 O(logn) 均摊时间内支持其他更通用的更新，例如反转子串和/或映射其符号。我们还可以使 FeST 使用紧凑空间，并将其扩展以将子串视为循环或它们的 ω 扩展。我们的 FeST 数据结构的 C++ 实现可在 https://github.com/fmasillo/FeST 获取。
Keyword:
Dynamic strings
Binary search trees
Splay trees
Dynamic data structures
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
1
论文数:
273
被引数:
1.0W
机构
引用论文
MARS: improving multiple circular sequence alignment using refined sequencesMARS: 使用精细序列改进多循环序列比对.png)
BMC GENOMICSOAAI
BMC GENOMICSIF3.7
OAAI分享收藏分享收藏
查看更多内容