模式匹配(也称为串匹配)是计算机科学中基本问题之一,已经广泛地应用到了生物研究、音乐信息检索和序列模式挖掘等各个领域。在模式匹配中,有的仅仅考虑最后一个模式子串在序列中匹配的位置,这种模式匹配称为宽松模式匹配;更为挑战性的问题是对每个模式串均考虑其在序列串中匹配的位置,而这种模式匹配称为严格模式匹配。严格模式匹配中近似模式匹配允许模式串与所匹配的序列串之间存在一定差异,增加了匹配的灵活性。本文研究的是具有Hamming距离的近似模式匹配。无重叠约束是要求任何两个出现中不能在相同位置处使用序列中相同字符。具有无重叠约束的模式匹配问题是指给定模式P在序列S中的所有出现集合中找到最大子集C,使得集合C中任意两个出现均是无重叠的出现。目前研究的模式匹配多为精确匹配,精确匹配要求每个字符必须匹配,一定程度上限定了匹配的灵活性。为此本文提出了无重叠约束的近似模式匹配问题(Approximate Pattern matching with Non-Overlapping constraints,APNO)。我们运用网树结构解决该问题,提出了NETLOR和NETROL算法,并对其改进提出了NETLORE和NETROLE算法。该算法在求解时,先将模式匹配问题转换为一棵网树,然后在网树中每次查找树根叶子路径,并将该路径所对应的解作为一个无重叠近似出现,之后依据树根叶子路径在网树的局部范围内进行快速剪枝,为下一次查找树根叶子路径做准备。最后大量实验验证了本文提出的四个算法的正确性,并且验证了NETLORE是更为高效的算法。