论文研究-求解PMWOC问题的位并行算法.pdf

带有灵活通配符和One-Off条件的模式匹配问题（pattern matching with flexible wildcards and One-Off condition，PMWOC）具有重要的理论意义和实际应用价值。给定带灵活通配符的模式和文本，目标是在线的计算模式在文本中的出现次数和匹配位置，这里要求任何两次出现不能共享文本同一位置，即One-Off条件。提出了一个基于位并行的搜索算法，采用了非确定有限自动机（nondeterministic finite automatons，NFA）对文本进行扫描。通过理论和实验证明，与其他解决相同问题的算法对比，该算法取得更好的时间性能和空间性能，而且不受模式长度变化和通配符间距变化影响。