关键词: 模式匹配，通配符，后缀树

Abstract: Pattern matching with wildcards is a hot research problem that can be used in biological sectuence analysis, text indexing, network intrusion detection, and so on. Aiming at the problem that the wildcards have strong limitations in the existing research work, pattern matching with flexible wildcards was studied. The wildcards can appear between any two substrings and can be specified with flexible length constraints. The nonlinear data structure-suffix tree was used to design build the suffix a completeness algorithm PAST. In the prepare process, an online incremental algorithm was used to tree which has priori knowledge of the text. In the search phase, the idea of dynamic programming was used to match the characters of the pattern. Experiments on DNA sectuences show that our method has better perfor mances in time than the related matching algorithm

Key words: Pattern matching, Wildcards, Suffix tree