论文标题
$ K $不匹配的二维独立
2-Dimensional Palindromes with $k$ Mismatches
论文作者
论文摘要
本文将二维palindrome搜索的问题扩展到近似匹配区域。使用锤距离作为措施，我们搜索最多$ k $不匹配的2D palindromes。我们考虑了两个不同的2D alindromes定义，并描述了这两种定义的有效算法。第一个定义意味着一个正方形，而第二个定义（也称为\ emph {Centrosymmmorericagrric fimals}）可以是任何矩形形状。给定大小$ n \ times m $的文本，第一种算法的时间复杂性为$ o（nm（\ log m + \ log n + k））$，对于第二个算法，它是$ o（nm（\ log m + k） + occ）$，$ occ $ occ $ occ $ occ $是输出的大小。
This paper extends the problem of 2-dimensional palindrome search into the area of approximate matching. Using the Hamming distance as the measure, we search for 2D palindromes that allow up to $k$ mismatches. We consider two different definitions of 2D palindromes and describe efficient algorithms for both of them. The first definition implies a square, while the second definition (also known as a \emph{centrosymmetric factor}), can be any rectangular shape. Given a text of size $n \times m$, the time complexity of the first algorithm is $O(nm (\log m + \log n + k))$ and for the second algorithm it is $O(nm(\log m + k) + occ)$ where $occ$ is the size of the output.
