论文标题
快速圆形图案匹配
Fast Circular Pattern Matching
论文作者
论文摘要
确切的圆形图案匹配（ECPM）问题包括报告文本$ t $中的图案$ p $的每一次旋转。在许多现实世界中，特别是在计算生物学上，圆形旋转是因为它们在病毒DNA中的突出而引起的。因此，鉴于对预处理时间的限制，许多研究领域的所有此类循环发生的速度都是有多速度。据我们所知，我们强调了ECPM问题的一种新颖方法，并介绍了伴随这种方法的四个数据结构，每种方法都以自己的时空权衡，除了实验性结果以确定最可行的数据结构。
The Exact Circular Pattern Matching (ECPM) problem consists of reporting every occurrence of a rotation of a pattern $P$ in a text $T$. In many real-world applications, specifically in computational biology, circular rotations are of interest because of their prominence in virus DNA. Thus, given no restrictions on pre-processing time, how quickly all such circular rotation occurrences is of interest to many areas of study. We highlight, to the best of our knowledge, a novel approach to the ECPM problem and present four data structures that accompany this approach, each with their own time-space trade-offs, in addition to experimental results to determine the most computationally feasible data structure.
