Strict Pattern Matching With General Gaps And Nonoverlapping Condition

Pattern matching is a classic problem in computer science,and has wide application value in many fields such as intrusion detection systems,pattern recognition,and sequence pattern mining.With the gradual increase of uncertain factors in application scenarios,traditional pattern matching can no longer meet the actual needs well,thus pattern matching with gap constraints appears.Pattern matching with gap constraints has an exponential solution space.In order to optimize the solution space,the nonoverlapping condition is introduced.Nonoverlapping pattern matching requires that the same element in the pattern string cannot be matched with the same sequence element.At present,most of the pattern matching with gap constraints is conducted under non-negative gap.The non-negative gap limits the order in which the patterns to be matched appear,reducing the practical value and flexibility of matching.In order to make the gap constraint more suitable to the actual needs,this paper addresses Nonoverlapping Pattern matching with General gap constraints(NPG).The main research contents and related work of this paper are as follows:(1)In the research of pattern matching with gap constraints,the NPG problem is proposed.This problem has three characteristics: strictly and exactly record the position of each character in the pattern string;the gap constraints between the sub-pattern strings al ow negative values;any two occurrences meet the nonoverlapping condition.(2)A general gap nettree is constructed on the basis of the nettree,and an efficient algorithm NetNPG is proposed.This algorithm first converts the NPG problem into a general gap nettree according to the target sequence and pattern.In order to reduce the time consumption caused by redundant pruning,a backtracking strategy is used to iteratively find the leftmost full path to obtain the largest nonoverlapping occurrence set.(3)Extensive experiments were performed on real biological data.The experimental results show the efficiency of the NetNPG algorithm.At the same time,the algorithm proposed in this paper is applied to sequence pattern mining and time series.Experimental results show that the general gap is more flexible than the non-negative gap.