模式串匹配是计算机科学中一个基本、重要的研究问题。随着信息技术的高速发展,它在Internet网络信息搜索、数据流挖掘、网络入侵检测、计算生物学等领域中的应用越来越广泛。近年来,带通配符约束的模式匹配问题作为模式匹配领域的一项新颖的研究方向已经越来越引起广泛的关注。在传统的模式中加入通配符约束,虽然使问题变得更复杂,但更能满足用户对模式的灵活定义的需求。这使得带通配符约束的模式匹配问题不仅具有理论研究价值,而且有着实际应用价值:如在生物信息学中,很多蛋白质模式便含有通配符约束。当前对带通配符的模式匹配存在的很多现有的工作,但仍然有一些问题需要进一步的研究,如在模式中通配符约束的定义,匹配结果的表达,时间效率的提高。为此,本文针对以上关键问题进行研究,主要工作如下:(1)本文在已有的工作基础上,介绍同时包括全局长度约束及局部通配符约束模式匹配问题的形式化定义,证明在One-Off条件下带通配符约束的模式匹配问题是一个NP-hard问题。(2)提出一种基于位并行技术的提出的BPBM算法。算法基于“最左最优”的启发式策略,返回One-Off条件下的所有匹配序列。该算法的基本思想是采用了BM算法的基于后缀搜索的方法,使用两个非确定性自动机NFA对扫描文本的过程进行模拟,并利用位并行技术解决了NFA当前活动状态比较多,对于每次读入的新字符更新活动状态集慢的缺陷。理论分析及实验证明BPBM算法较解决同类或类似问题的其他算法无论在时间上或匹配结果上更具竞争力。(3)最后给出一个本课题的网站系统设计,包含本课题的一些研究的算法演示,为今后研究更加深入的研究提供一个平台。