给定一个大小为ｎ×ｎ的文本Ｔ和一个大小为ｍ×ｍ的模板Ｐ，如果文本Ｔ中存在一个ｍ×ｍ的子块与模板Ｐ能够逐点匹配，称为精确匹配。如果最多有ｋ个元素不同，称为带有最多ｋ个误差的近似匹配。对于精确匹配，本文给出了一个时间复杂性为Ｏ（ｎ２ｌｏｇ｜∑｜）的算法，∑＝｛ａ１，２，…，ａ｜∑｜｝，是模板的字符集。对于近似匹配，快速算法分为两步：（１）预选。利用精确匹配算法找出能精确匹配的ｓ×ｓ（０≤ｓ≤ｍ）子块，得到ｈ个候选的对准点；（２）验证。把模板对准候选点，逐点比较，以确定不相同的元素是否不超过ｋ个。近似匹配的时间

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.