【摘要】 带有通配符的模式匹配问题(PMWL)模式定义的灵活性给用户提供方便,却也造成求解上的困难.目前没有任何多项式算法能得到该问题的完备解,同时也缺少足够的完备性分析.文中认为模式特征是影响PMWL完备性的关键因素,并提出模式重复度的概念,记为rep.证明在rep=0的限定条件下PMWL的完备性,同时分析rep>0时PMWL不完备的原因.实验以近似比为指标,说明rep对PMWL完备性的影响.更多还原

【Abstract】 Pattern matching with wildcards and length constraints(PMWL) provides more convenience to users since its flexibility in definition which also leads to difficulties in solving problem.Currently,to our knowledge,no polynomial algorithms obtain the complete solution of this problem,and the analysis for completeness is far from sufficient.In this paper,the pattern feature is proved to be the key factor for the completeness of PMWL and a concept,denoted as rep,is provided which measures the repetitions in the pattern.The completeness of PMWL is proved under a certain condition when rep=0.And the reason of incompleteness under the condition of rep>0 is also explained clearly.In the experiments,approximation ratio is utilized as a measurement to demonstrate the impact of rep on the PMWL problem.更多还原