Finding approximate palindromes in strings
Finding approximate palindromes in strings
复制标题
寻找字符串中的近似回文
DOI：
10.1016/s0031-3203(01)00179-0
复制
发表时间：
2002
期刊：
影响因子：
--
通讯作者：
V. Barbosa
中科院分区：
文献类型：
--
作者：
Alexandre H. L. Porto;V. Barbosa
我们引入了字符串中近似回文的新颖定义，并提供了一种算法来查找字符串中最多有 k 个错误的所有最大近似回文。我们的定义基于近似模式匹配的常见编辑操作，并且对于固定字母表上大小为 n 的字符串，我们给出的算法运行时间为 O(k2n)。我们还讨论了两种与实现相关的算法改进，并通过实验和平均案例分析证明了它们在实践中的有效性。
We introduce a novel definition of approximate palindromes in strings, and provide an algorithm to find all maximal approximate palindromes in a string with up to k errors. Our definition is based on the usual edit operations of approximate pattern matching, and the algorithm we give, for a string of size n on a fixed alphabet, runs in O(k2n) time. We also discuss two implementation-related improvements to the algorithm, and demonstrate their efficacy in practice by means of both experiments and an average-case analysis.