Given a text of size n×n and a pattern of size m×m

the exact-matching is to find all occurrence of the pattern in the text

while the approximate-matching is to find all the location of m×m blocks in the text that differ by at most k mismatches. We present a new approach for exact-matching

which runs in O( n 2lo g?Σ?)

Σ = { a1

a2

?

a?Σ?} is the alphabet of the pattern

and for approximate-matching

inO( n2lo g?Σ?) + hm2)

which consists of two stages. The first stage is to preselect h subblocks of size s×s ( 0≤s≤m) that exactly match the pattern. And the second stage of verification compares the blocks containing these h subblocks to determine if the mismatches is no more than k.