  Pattern matching is a fundamental process in almost every scientific domain.
The problem involves finding the positions of a given pattern (usually of short
length) in a reference stream of data (usually of large length). The matching
can be an exact or as an approximate (inexact). Exact matching is to search for
the pattern without allowing for mismatches (or insertions and deletions) of
one or more characters in the pattern), while approximate matching is the
opposite. For exact matching, several data structures that can be built in
linear time and space are used and in practice nowadays. For approximate
matching, the solutions proposed to solve this matching are non-linear and
currently impractical. In this paper, we designed and implemented a structure
that can be built in linear time and space ($O(n)$) and solves the approximate
matching problem in $O(m + \frac {log_2n {(log_\Sigma n)} ^{k+1}}{k!} + occ)$
search costs, where $m$ is the length of the pattern, $n$ is the length of the
reference, and $k$ is the number of tolerated mismatches (and insertion and
deletions).
