在模式识别问题中引入通配符这种特殊字符以匹配字母表中的任意字符,从而形成了带有通配符模式匹配这一新的研究方向,在计算生物学、信息检索等研究领域得到了广泛关注。然而,上述领域的大量研究表明,频繁共现在一段文本区域内的多个模式之间表现为某种模式形式。比如在DNA序列中,TATA序列作为内含子的起始标志常出现在CAATCT序列下游30-50 bp的位置,这两个子序列共同组成的模式可提高序列特异性,可以标记为“一.CAATCT[30,50]TATA..."。上述情况可进一步推广为子模式序列集,其中两个相邻子模式的间隔在一定长度范围内,为表示这种灵活的位置间隔,将通配符从指代单个字符扩展为指代一定长度的子串,称此通配符为限长空位(Bounded length gaps)。另外,通过引入one-off约束以保证子模式序列集的稳定性,避免了个别子模式异常的出现次数影响子模式集的匹配。由此而得到了带有限长空位和one-off约束的模式匹配(PMGO)问题。本文围绕PMGO问题,开展了一系列相关的研究工作,主要研究成果包括以下几个方面：(1)借鉴约束可满足问题框架,对PMGO问题建立求解模型。模型由变量、值域和约束条件构成三元组,并运用形式化语言描述了问题的限长空位、约束条件和解空间等主要概念,同时说明了PMGO问题的基本性质,其中包括在特殊条件下的完备性和相邻匹配解在文本中的位置关系。另外,针对限长空位使得匹配问题形成了多分支的解结构,借助模型说明了在此解空间中搜索满足one-off约束的最优解为组合优化问题；(2)提出一种求解PMGO问题的启发式搜索算法。首先,定义了解空间的划分边界,提出了采用分治策略的解空间划分算法SPLIT,将PMGO问题等价划分为若干独立的子问题,并从理论上说明了划分前后的解结构等价。实验结果表明了SPLIT算法可有效降低非线性匹配算法的时间消耗。其次,将划分后的子问题转化为图结构下的路径搜索问题,其中自顶层到底层的路径集合为解空间,而彼此独立的路径子集为匹配解集,并证明了问题转化前后求解的等价性。之后,提出一种启发式路径搜索算法GPM,根据one-off约束得到节点之间的约束关系,再迭代交互的进行剪枝与搜索,且GPM算法的输出即为PMGO问题的解。实验部分使用匹配解丢失率度量已有启发式算法和GPM算法的完备性,结果表明GPM算法可以与已有启发式算法形成互补,有效降低匹配解丢失率；(3)给出了PMGO问题在特定条件下的完备性分析和求解算法。首先,将模式重复度作为一种模式特征,研究了以下两种情况的求解。一方面针对模式中无重复字符的情况,说明了使用贪心搜索策略可得到PMGO问题的完备解,该结论适用于GPM算法和已有启发式算法,实验部分以近似比为指标进一步说明了重复度对问题完备性的影响；另一方面,对于尾部带有重复字符模式串,提出了一种基于动态剪枝策略的小兵算法,实验结果表明小兵算法有效提高了匹配解的质量。