Journal article
Frequency covers for strings
Fundamenta Informaticae, Vol.163(3), pp.275-289
2018
Abstract
We study a central problem of string processing: the compact representation of a string by its frequently-occurring substrings. In this paper we propose an effective, easily-computed form of quasi-periodicity in strings, the frequency cover; that is, the longest of those repeating substrings u of w, |u| > 1, that occurs the maximum number of times in w. The advantage of this generalization is that it is not only applicable to all strings but also that it is the only generalized notion of cover yet proposed, which can be computed efficiently in linear time and space. We describe a simple data structure called the repeating substring frequency array (ℛ
Details
- Title
- Frequency covers for strings
- Authors/Creators
- N. Mhaskar (Author/Creator)W.F. Smyth (Author/Creator)P. Charalampopoulos (Author/Creator)M. Crochemore (Author/Creator)S.P. Pissis (Author/Creator)
- Publication Details
- Fundamenta Informaticae, Vol.163(3), pp.275-289
- Publisher
- IOS Press
- Identifiers
- 991005544831207891
- Murdoch Affiliation
- School of Engineering and Information Technology
- Language
- English
- Resource Type
- Journal article
Metrics
76 Record Views
InCites Highlights
These are selected metrics from InCites Benchmarking & Analytics tool, related to this output
- Collaboration types
- Domestic collaboration
- International collaboration
- Citation topics
- 4 Electrical Engineering, Electronics & Computer Science
- 4.182 Data Structures, Algorithms & Complexity
- 4.182.1103 Efficient Algorithms
- Web Of Science research areas
- Computer Science, Software Engineering
- Mathematics, Applied
- ESI research areas
- Computer Science