带可变长度空位和一次性条件的模式匹配

• 作者: 田芳
• 来源期刊: 合肥学院学报：自然科学版
• 学科: 工学
• 关键词: 可变长度空位 一次性条件 网树 模式匹配
• 年，卷（期）: 2014,（4）
• 页码范围: 50-56
• 页数: 7页
• 分类号: TP301

摘要

带可变长度空位和一次性条件的模式匹配是一种带通配符长度约束的模式匹配问题，主要目标是寻找模式在序列中的最多出现，要求序列中任何位置只能被使用一次。提出了一种基于网树在线的启发式算法，该算法首先通过模式中子模式的出现位置构建网树；然后，从网树上选择使用次数最小的节点作为出现的位置；最后，对网树进行修剪，以达到满足一次性条件和加快搜索效率的目的。通过理论分析，该算法有更好的时间复杂度和空间复杂度。通过真实生物数据进行实验，实验结果表明，该算法与其他在线算法进行对比，可以获得更多的出现次数和更好的时间性能。

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	田芳	安徽水利水电职业技术学院电子信息工程系	4	1	1.0	1.0