.png){kind=icon}
返回
String Matching with a Dynamic Pattern
.png){kind=icon}
PRE
AI
DOI：10.1007/978-3-032-05228-5_17.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
在本工作中，我们处理字符串匹配问题的一个自然变体，即针对动态模式的情况：给定静态文本T和模式P，我们希望支持对模式的字符插入和删除操作，并在每次操作后计算其在文本中出现的次数。我们展示了一种使用后缀数组的简单且实用的算法，该算法在O(|T|)预处理时间后实现O(log|T|)的更新时间。我们展示了如何将我们的解决方案扩展以支持子串删除、转置（将子串移动到模式的另一位置）和复制（复制子串并粘贴到特定位置），且在相同的时间复杂度下。我们的解决方案还可以扩展以支持在线文本（在文本一端插入字符），同时保持相同的摊销界限。
Keyword:
Strings
Algorithms
Suffix array
String matching
期刊
S
IF:
0
论文数:
22
被引数:
0
机构
引用论文
.png){kind=icon}
分享收藏
查看更多内容