Abstract:

In order to improve the performance of the dynamic programming algorithm,a traditional method of solving the approximate pattern matching problem, a novel filtering-type approximate pattern matching algorithm is proposed,which combines the advantages of the dynamic programming algorithm, splits the pattern string into smaller pattern pieces with the same length,divides the text string to be matched into sub-strings and further establishes the corresponding index. Moreover,a new filtering strategy is proposed to eliminate the redundancy of the match examination. Example results show that the proposed algorithm is superior to the existing ones due to its small match time cost and high performance,especially under the condition of long pattern string matching; and that,as compared with the traditional dynamic programming algorithm,the proposed algorithm reduces the match time by more than 50% when the pattern string length is more than 45.

Key words: approximate pattern matching, dynamic programming algorithm, matching time