带可变长度通配符的模式匹配算法

针对目前已有的算法在计算带有可变长度通配符的模式在文本中的出现次数问题时，需要的时间是多项式级别，而且受文本长度、模式长度和通配符间距的影响比较大。提出了一种基于Aho-Corasick自动机的AAI（pAttern mAtching with wIldcards） 算法，计算中采用了动态规划思想和有效的修剪技术。AAI算法的时间复杂度和空间复杂度分别为[O(n+m+α)]和[O(m+B)]，其中[n]和[m]分别表示文本和模式的长度，[α]是所有子模式在文本中出现的数目，[B]是模式中通配符间距下限的总和。通过真实数据和人工数据的实验结果表明，AAI算法与同类算法相比具备显著的优势。

Pattern matching with variable length wildcards

Current works on computing the number of all matches of pattern with variable length wildcards in text need polynomial time, and have been greatly influenced by the length of the text, pattern, and wildcards interval. This paper proposes an algorithm AAI（pAttern mAtching with wIldcards） based on Aho-corasick automaton which adopts dynamic programming and effective pruning strategies. Let n and m be the length of P and T, respectively. The algorithm AAI need time[O(n+m+α)]and space[O(m+B)], where α is the total number of occurrences of the subpatterns in P within S, B is the sum of the lower bonds of the wildcards. Experimental results from different aspects validate that AAI is more stable and effective than other peers on both artificial and real-world data.