We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Efficient string matching with wildcards and length constraints.
- Authors
Chen, Gong; Wu, Xindong; Zhu, Xingquan; Arslan, Abdullah; He, Yu
- Abstract
This paper defines a challenging problem of pattern matching between a pattern P and a text T, with wildcards and length constraints, and designs an efficient algorithm to return each pattern occurrence in an online manner. In this pattern matching problem, the user can specify the constraints on the number of wildcards between each two consecutive letters of P and the constraints on the length of each matching substring in T. We design a complete algorithm, SAIL that returns each matching substring of P in T as soon as it appears in T in an O( n+ klmg) time with an O( lm) space overhead, where n is the length of T, k is the frequency of P's last letter occurring in T, l is the user-specified maximum length for each matching substring, m is the length of P, and g is the maximum difference between the user-specified maximum and minimum numbers of wildcards allowed between two consecutive letters in P.
- Subjects
ALGORITHMS; CONSTRAINT satisfaction; TEXT files; ARTIFICIAL intelligence; COMPUTER programming
- Publication
Knowledge & Information Systems, 2006, Vol 10, Issue 4, p399
- ISSN
0219-1377
- Publication type
Article
- DOI
10.1007/s10115-006-0016-8