Conference paper
String regularities with don't cares
Prague Stringology Conference 2002 (Czech Technical University, Prague, 23/09/2002–24/09/2002)
2002
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 A, an O(n log n log |A|) 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. Iliopoulos (Author/Creator)M. Mohamed (Author/Creator)L. Mouchard (Author/Creator)K.G. Perdikuri (Author/Creator)W.F. Smyth (Author/Creator)A.K. Tsakalidis (Author/Creator)
- Conference
- Prague Stringology Conference 2002 (Czech Technical University, Prague, 23/09/2002–24/09/2002)
- Identifiers
- 991005544431207891
- Murdoch Affiliation
- Murdoch University
- Language
- English
- Resource Type
- Conference paper
Metrics
132 File views/ downloads
77 Record Views