改进的带可变长度通配符的近似模式串匹配算法

针对处理可变长度通配符的近似模式串匹配传统算法结果质量不高、易丢解等问题,提出1种启发式的文本-模式倒置算法。基于动态规划思想采用文本-模式倒置策略,搜索得到符合匹配条件子串的开始位置并划分候选集。通过获取初始解、集合划分及优化组合2个过程,筛选出匹配子串的最优解。与同类动态规划(DP)和Sail-Approx算法进行实验对比,结果表明该文算法解的平均增长率为21.9%。