近似迴文子序列查詢演算法

Abstract

給定一個長度為n的字串T以及一個正整數k，我們設計出一個有效率的演算法，對於字串T進行前處理後，可以在後續指定的任意子字串中快速找出該範圍內最長的近似迴文。近似迴文在此定義為左右兩半至多有k 個不對稱字元的字串。我們設計出的演算法在前處理所需的時間及空間複雜度分別為O(kn)以及O(n)，後續每次查詢某段範圍內最長近似迴文所需要的計算時間為O(log log n)。

Given an input string T of length n and an integer k, we study how to find the longest k-mismatch palindromic substring within a range specified by each query. For this problem, we propose an algorithm with O(kn) preprocessing time and O(n) space, enabling each query to be answered in O(log log n) time on the word RAM model.