Search
 
loader loading subjects...
cover
Approximate String Matching Problem under Non-Overlapping Inversion Distance
Shih-Yuan Huang, Chung-Han Yang, Toan Thang Ta, Chin Lung Lu
40 - 48
10.3233/978-1-61499-484-8-40
Frontiers in Artificial Intelligence and Applications
Volume 274: Intelligent Systems and Applications
Abstract

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(nm2) time and O(m2) space, where n is the length of the text and m is the length of the pattern.

$35.00 / €27.50 / £22.00
Add PDF to cart