Pattern Matching with Wildcards and Length Constraints

摘要0514819主要研究者：Xindong Wu;共同主要研究者：Abdullah N. Arslan和Xingquan ZhuU，Vermont State Agricultural College本研究定义了一个具有通配符和长度约束的模式匹配问题，旨在设计有效的算法来解决这个问题。 给定一个模式P和一个文本T，T中的子串S是P的匹配串，如果（1）S中每两个连续模式字母之间的通配符的数量和（2）S的长度都由用户的指定限制。 该项目试图找到P在T中出现的“独特”的最大数量。 这是一个复杂的问题，它集成了两个局部约束（以连续模式字母之间的间隙的形式）和模式匹配中的全局长度约束。研究团队将从现有的初步设计开始，进一步研究模式匹配问题，通过（1）探索问题的时间复杂性，（2）设计新的高效算法来处理一些特殊情况，（3）将这些高效算法应用于文本索引、基因序列分析、网络安全和流数据挖掘等实际问题中。

ABSTRACT0514819PI: Xindong Wu; Co-PIs: Abdullah N. Arslan and Xingquan ZhuU of Vermont & State Agricultural CollegePattern Matching with Wildcards and Length ConstraintsThis research defines a unique problem of pattern matching with wildcards and length constraints, and aims to design efficient algorithms for the problem. Given a pattern P and a text T, a substring S in T is a matching string of P if (1) the number of wildcards between each two consecutive pattern letters in S and (2)the length of S are both bounded by the user's specifications. The project seeks to find the maximum number of ``distinct'' occurrences of P in T. This is a complex problem that integrates both local constraints(in the form of gaps between consecutive pattern letters) and global length constraints in pattern matching.The research team will start with an existing preliminary design and further investigate the pattern matching problem, by (1) exploring the time complexity of the problem, (2) designing new, efficient algorithms to deal with some special cases, and (3) applying these efficient algorithms in practical problems in text indexing, gene sequence analysis, network security and stream data mining.