String regularities with don't cares

C.S. Ilopoulos; M. Mohamed; L. Mouchard; W.F. Smyth; K.G. Perdikuri; A.K. Tsakalidis

Back

Journal article

Peer reviewed

String regularities with don't cares

C.S. Ilopoulos, M. Mohamed, L. Mouchard, W.F. Smyth, K.G. Perdikuri and A.K. Tsakalidis

Nordic Journal of Computing, Vol.10(1), pp.40-51

2003

Files and links (1)

url

Link to Published Version *Subscription may be requiredView

Abstract

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.

Details

Title: String regularities with don't cares
Authors/Creators: C.S. Ilopoulos (Author/Creator)
M. Mohamed (Author/Creator)
L. Mouchard (Author/Creator)
W.F. Smyth (Author/Creator)
K.G. Perdikuri (Author/Creator)
A.K. Tsakalidis (Author/Creator)
Publication Details: Nordic Journal of Computing, Vol.10(1), pp.40-51
Publisher: ACM Digital Library
Identifiers: 991005540685407891
Murdoch Affiliation: Murdoch University
Language: English
Resource Type: Journal article

Metrics

71 Record Views