Abstract
In this thesis, 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. First, 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. Next, we present another algorithm based on an efficient filtering strategy that has the same worst-case time and space complexities as the first algorithm.