Murdoch University Research Repository

Welcome to the Murdoch University Research Repository

The Murdoch University Research Repository is an open access digital collection of research
created by Murdoch University staff, researchers and postgraduate students.

Learn more

String regularities with don't cares

Ilopoulos, C.S., Mohamed, M., Mouchard, L., Smyth, W.F., Perdikuri, K.G. and Tsakalidis, A.K. (2003) String regularities with don't cares. Nordic Journal of Computing, 10 (1). pp. 40-51.

Link to Published Version:
*Subscription may be required


We describe algorithms for computing typical regularities in strings x = x[1..n] that contain don't care symbols. For such strings on alphabet Σ, an O(n log n log |Σ|) worst-case time algorithm for computing the period is known, but the algorithm is impractical due to a large constant of proportionality. We present instead two simple practical algorithms that compute all the periods of every prefix of x; our algorithms require quadratic worst-case time but only linear time in the average case. We then show how our algorithms can be used to compute other string regularities, specifically the covers of both ordinary and circular strings.

Item Type: Journal Article
Publisher: ACM Digital Library
Copyright: © 2003 ACM
Item Control Page Item Control Page