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.
翻译：准确的循环模式匹配问题包括:每发生一个模式的轮换,就报告一次,以美元计值,以美元计值;在许多实际应用中,特别是在计算生物学中,循环轮换因其在病毒DNA中的突出地位而引起关注;因此,在未限制处理前时间的情况下,许多研究领域都对此类循环周期的发生有多快感兴趣;我们据我们所知,强调对ECPM问题的一种新办法,并提出了伴随这一办法的四个数据结构,每个结构都有各自的时间空间取舍,此外还有确定最可行的计算数据结构的实验结果。
相关内容
微信扫码咨询专知VIP会员