标题： 改进的循环词典匹配 显示英文标题

标题： Improved Circular Dictionary Matching

摘要： 圆字符串字典匹配问题是对经典的字典匹配问题的扩展，在这个问题中，字典中的每个字符串都被解释为一个圆字符串：读取字符串的最后一个字符后，我们可以回到它的第一个字符。 圆字符串字典匹配问题源于生物信息学和计算几何中的应用。 2011年，Hon等人。 [ISAAC 2011] 展示了如何通过利用Mantaci等人的eBWT和Sadakane的压缩后缀树，在压缩空间内高效解决圆字符串字典匹配查询。 该解决方案基于以下假设：字典中的所有字符串都是不同的且非周期性的，没有一个字符串是另一个字符串的圆旋转，字典中的字符串长度相似。 在本文中，我们考虑任意字典，并展示了如何在压缩空间内使用$ n \log \sigma (1 + o(1)) + O(n) + O(d \log n) $位在$ O((m + occ) \log n) $时间内解决圆字符串字典匹配查询，其中$ n $是字典的总长度，$ m $是模式的长度，$ occ $是出现次数，$ d $是字典中的字符串数量，$ \sigma $是字母表的大小。 我们的解决方案基于后缀数组到任意字典的扩展以及受最近图索引和压缩结果启发的字典LCP数组的采样机制。 显示英文摘要

摘要： The circular dictionary matching problem is an extension of the classical dictionary matching problem where every string in the dictionary is interpreted as a circular string: after reading the last character of a string, we can move back to its first character. The circular dictionary matching problem is motivated by applications in bioinformatics and computational geometry. In 2011, Hon et al. [ISAAC 2011] showed how to efficiently solve circular dictionary matching queries within compressed space by building on Mantaci et al.'s eBWT and Sadakane's compressed suffix tree. The proposed solution is based on the assumption that the strings in the dictionary are all distinct and non-periodic, no string is a circular rotation of some other string, and the strings in the dictionary have similar lengths. In this paper, we consider arbitrary dictionaries, and we show how to solve circular dictionary matching queries in $ O((m + occ) \log n) $ time within compressed space using $ n \log \sigma (1 + o(1)) + O(n) + O(d \log n) $ bits, where $ n $ is the total length of the dictionary, $ m $ is the length of the pattern, $ occ $ is the number of occurrences, $ d $ is the number of strings in the dictionary and $ \sigma $ is the size of the alphabet. Our solution is based on an extension of the suffix array to arbitrary dictionaries and a sampling mechanism for the LCP array of a dictionary inspired by recent results in graph indexing and compression.