模式特征对带有通配符和长度约束的模式匹配问题的影响

摘要

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