关键词: 模式匹配, 间隙约束, 无重叠条件, 在线算法, 网树

Abstract:

Pattern matching under the nonoverlapping condition is one of many pattern matching algorithms for gap constraint problems.Although it is proved that pattern matching under the nonoverlapping condition is a polynomial time complexity problem and an effective solving algorithm is proposed, the current solving algorithm adopts offline calculation, which has the disadvantage of high spatial complexity.In order to solve this problem, this paper designs an online solving algorithm. The algorithm reads the sequence string and finds the root-leaf path in the flow net tree that meets the constraint conditions, which realizes fast pruning of useless nodes and thus speeds up the matching speed.Compared with the spatial complexity of the offline algorithm, the spatial complexity of the online algorithm is O(m×maxlen×W), where m, maxlen, and W represent the pattern string length, the maximum pattern length constraint and the maximum gap constraint, respectively.Experimental results not only verify the completeness of our proposed algorithm, but also demonstrate that it consumes less memory than the existing algorithm.

Key words: pattern matching, gap constraint, nonoverlapping condition, online algorithm, Nettree