文件名称：带可变长度通配符的模式匹配算法 (2015年)
文件大小：1.16MB
文件格式：PDF
更新时间：2024-06-15 05:50:07
工程技术 论文
针对目前已有的算法在计算带有可变长度通配符的模式在文本中的出现次数问题时,需要的时间是多项式级别,而且受文本长度、模式长度和通配符间距的影响比较大。提出了一种基于Aho-Corasick自动机的AAI(pAttern mAtching with wIldcards)算法,计算中采用了动态规划思想和有效的修剪技术。AAI算法的时间复杂度和空间复杂度分别为O(n+m+α)和O(m+B),其中n和m分别表示文本和模式的长度,α是所有子模式在文本中出现的数目,B是模式中通配符间距下限的总和。通过真实数据和人工数据