论文标题
内部quasiperiod查询
Internal Quasiperiod Queries
论文作者
论文摘要
内部模式匹配需要一个人回答有关给定字符串因素的查询。回答内部时期查询，要求给定因素的时期，许多结果已知。在本文中，我们（首次）调查了给定因子的覆盖物（也称为Quasiperiods）的内部查询。我们提出了一个数据结构，该数据结构在$ o（\ log n \ log \ log \ log n）$最短封面中的时间和$ o（\ log n（\ log \ log n）^2）$（在$ o（\ log \ log n）^2）中表示所有封面后的时间，在$ o（n \ log n）$时间和空间的时间和空间预处理后。
Internal pattern matching requires one to answer queries about factors of a given string. Many results are known on answering internal period queries, asking for the periods of a given factor. In this paper we investigate (for the first time) internal queries asking for covers (also known as quasiperiods) of a given factor. We propose a data structure that answers such queries in $O(\log n \log \log n)$ time for the shortest cover and in $O(\log n (\log \log n)^2)$ time for a representation of all the covers, after $O(n \log n)$ time and space preprocessing.
