.png){kind=icon}
返回
Dynamic Pattern Matching with Wildcards
.png){kind=icon}
PRE
AI
DOI：10.4230/LIPIcs.STACS.2026.68.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
我们研究了完全动态的模式匹配问题，其中模式可能包含最多k个通配符符号，每个通配符可以匹配字母表中的任何符号。文本和模式都受到更新（插入、删除、更改）的影响。我们设计了一个预处理时间为O(n log² n)、更新/查询时间为Õ(kn(k/(k+1)) + k² log n)的算法。该界限对于常数k是真正的次线性，当k=o(log n)时也是次线性。我们进一步补充了条件下界：假设预处理时间为亚二次方，对于k=Ω(log n)的情况实现真正的次线性更新时间将与强指数时间假设（SETH）矛盾。最后，我们为两种特殊情况开发了次线性算法：如果模式包含w个非通配符符号，我们给出预处理时间为O(nw)、更新时间为O(w + log n)的算法，只要w是真正的次线性，该算法就是真正的次线性。通过结合快速傅里叶变换（FFT）技术和块分解，我们为最多有两个非通配符的情况设计了一个确定性真正的次线性算法，其预处理时间为O(n^1.8)，更新时间为O(n^0.8 log n)。
Keyword:
pattern matching
wildcards
dynamic algorithms
string algorithms
data structures
期刊
机构
引用论文
暂无论文信息