Abstract: With the developments in bioinformatics and information retrieval,pattern matching with wildcards and length constraints has attracted wild attention．This problem extends the exact pattern matching,so it brings more flexibility as well as complexity．Meanwhile,the time complexity of non-linear algorithms is greatly increased．The solution space makes great difference to the efficiency of matching algorithms,but the characteristics of the problem solution space is still lack of systematic research．Therefore,the problem solution space was presented,and the divisibility of the space was analyzed．Afterwards,a solution space partitioning algorithm,named SPLIT,was proposed,and its time complexity was also illustrated．In our experiments,three pattern matching algorithms were used as baselines running on realDNA data sets with 5109 sets of patterns．Our empirical results verify that SPLIT can effectively reduce the time consumption of non-linear matching algorithms without influencing the matching solution.

Key words: Solution space,Partitioning,Pattern matching,Wildcard