Browsing by Author "Ta, Toan Thang"

Now showing 1 - 1 of 1

Approximate String Matching Problem under Non-Overlapping Inversion Distance
(2015-01-01)
Huang, Shih-Yuan
;
Yang, Chung-Han
;
Ta, Toan Thang
;
Lu, Chin Lung
;
生物資訊及系統生物研究所
In this paper, we introduce and study the approximate string matching problem under non-overlapping inversion distance. Given a text t, a pattern p and a non-negative integer k, the goal of the problem is to find all locations in the text t that match the pattern p with at most k non-overlapping inversions. As a result, we use the dynamic programming approach to design an algorithm that solves this problem in O(nm(2)) time and O(m(2)) space, where n is the length of the text and m is the length of the pattern.