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

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

Pattern Matching with Variable-Length Gaps and The One-off Condition

Pattern matching with variable‐length gaps and the one‐off condition is a problem of pattern matching with wildcards ,which aim to find the maximal number of occurrences of a pattern in a sequence under the one‐off condition ,namely ,each character in the given sequence can be used at most once in all occurrences of a pattern . The paper designs a heuristic algorithm based on nettree online .The algorithm constructs a nettree through the occurrence positions of subpatterns of pattern first ;and then selects less used node from nettree be the position of one occurrence ;finally ,prunes the nettree to achieve satisfing one‐off condition and improving search efficiency . Experimental results demonstrate that the algorithm achieves more occurrences than any other online algorithm .Meanwhile ,theory and experiment show that the algorithm has better time and space performance .