摘 要：带通配符的模式匹配问题具有更广阔的应用前景。间隙约束是将通配符的数量设置为一个可变范围，具有更高的灵活性。一次性模式匹配作为带间隙约束模式匹配的一种，能够对匹配结果进行有效的缩减，有着重要的实际应用意义。本文主要综述了目前一次性序列模式匹配相关研究，并对将来的研究工作进行了展望。

关键词：一次性;间隙约束;模式匹配

模式匹配是计算机科学中的一个重要研究方向。带通配符的模式匹配不仅具有理论研究意义，而且在生物基因检测、序列模式挖掘、文本信息搜索等领域具有重要的应用。然而，传统通配符的数目通常是单个或固定值，在间隔不确定字符数时无法适用。而更灵活的间隙约束采用了指定范围来描述模式中的通配符数量，可以表示为P=p1[a1，b1]p2…pj[aj，bj]pj+1…pm1[am1，bm1]pm，其中，[aj，bj]就是间隙约束，aj和bj分别指pj和pj+1之间通配符个数的最小值和最大值[1]。

一次性模式匹配作为带间隙约束模式匹配中的一种，不仅能够对结果集进行有效缩减，而且在序列模式挖掘中具有重要應用[2]。由于间隙约束的存在，每当子模式出现不同的位置，都会产生一个新的出现，从而导致解的空间大小达到指数级。设序列长度为n，模式长度为m，最大间隙为w，则解的空间大小为O（nwm），当模式长度m较大时，所有出现的数量将无法估计。为了解决该问题，武等人[3]研究了一次性条件的模式匹配，一次性条件规定序列中的字符最多只能被匹配一次，解的空间大小降低到O（n/m）。……