Abstract: Abstract Most of the existing Approximate String Matching （ASM） algorithms can determine the similarity of strings by computing the minimal number of mismatching characters （edition distance） between them, while the problem that deciding whether at least

Key words: Approximate string matching, Dynamic programming, Section policy, Trace back policy