作者：武优西; 王博; 高雪冬模式匹配间隙约束无重叠条件在线算法网树
摘要：无重叠条件模式匹配是众多间隙约束的模式匹配算法中的一种,尽管当前证明了无重叠条件模式匹配是一个多项式时间复杂度问题,并提出了有效的求解算法,但是当前求解算法采用离线计算方式,具有空间复杂度较高的缺点。为了解决该问题,设计了一种在线求解算法,该算法一边读入序列串,一边在流网树中寻找符合约束条件的树根-树叶路径,以快速剪枝无用节点,从而加快了匹配速度。与离线算法的空间复杂度相比,在线算法的空间复杂度为O(m×maxlen×W),这里m,maxlen和W分别表示模式串长度、模式最大长度约束和最大间隙约束。实验结果不仅验证了算法的完备性,与现有算法相比,在内存占用上均有较大性能的提升。
注：因版权方要求，不能公开全文，如需全文，请咨询杂志社
