Efficient string matching with wildcards and length constraints

Chen, G; Wu, X; Zhu, X; Arslan, AN; He, Y

Efficient string matching with wildcards and length constraints

Chen, G Wu, X Zhu, X Arslan, AN He, Y

Permalink

Publication Type:: Journal Article
Citation:: Knowledge and Information Systems, 2006, 10 (4), pp. 399 - 419
Issue Date:: 2006-11-01

Closed Access

	Filename	Description	Size
	2011000605OK.pdf		457.66 kB	Adobe PDF	View/Open

Copyright Clearance Process

Recently Added
In Progress
Closed Access

This item is closed access and not available.

Full metadata record

Field	Value	Language
dc.contributor.author	Chen, G	en_US
dc.contributor.author	Wu, X	en_US
dc.contributor.author	Zhu, X	en_US
dc.contributor.author	Arslan, AN	en_US
dc.contributor.author	He, Y	en_US
dc.date.issued	2006-11-01	en_US
dc.identifier.citation	Knowledge and Information Systems, 2006, 10 (4), pp. 399 - 419	en_US
dc.identifier.issn	0219-1377	en_US
dc.identifier.uri	http://hdl.handle.net/10453/15139
dc.description.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. © Springer-Verlag London Limited 2006.	en_US
dc.relation.ispartof	Knowledge and Information Systems	en_US
dc.relation.isbasedon	10.1007/s10115-006-0016-8	en_US
dc.subject.classification	Information Systems	en_US
dc.title	Efficient string matching with wildcards and length constraints	en_US
dc.type	Journal Article
utslib.citation.volume	4	en_US
utslib.citation.volume	10	en_US
utslib.for	0801 Artificial Intelligence and Image Processing	en_US
utslib.for	0806 Information Systems	en_US
pubs.embargo.period	Not known	en_US
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	/University of Technology Sydney/Strength - AAI - Advanced Analytics Institute Research Centre
utslib.copyright.status	closed_access
pubs.issue	4	en_US
pubs.publication-status	Published	en_US
pubs.volume	10	en_US

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. © Springer-Verlag London Limited 2006.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/15139