| Popis: |
Given a text of size n/spl times/n and a pattern of size m/spl times/m, the exact matching is to find all occurrences of the pattern in the text, while the approximate matching is to find all the locations of m/spl times/m blocks in the text that differ by at most k mismatches. We present a new algorithm for exact matching, which runs in O(n/sup 2/ log|/spl Sigma/|), /spl Sigma/={a/sub 1/,a/sub 2/,...a/sub |/spl Sigma/|/} is the alphabet of the pattern, and for approximate matching, in O(n/sup 2/ log|/spl Sigma/|+hm/sup 2/), which consists of two stages. The first stage is to preselect h subblocks of size s/spl times/s, 0/spl les/s/spl les/m that exactly match the pattern. The second stage of verification compares the blocks containing these h subblocks to determine if the number of mismatches is less than k. |
