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

Frequency covers for strings

Mhaskar, N., Smyth, W.F., Charalampopoulos, P., Crochemore, M. and Pissis, S.P. (2018) Frequency covers for strings. Fundamenta Informaticae, 163 (3). pp. 275-289.

Link to Published Version:
*Subscription may be required


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 (ℛ

Item Type: Journal Article
Murdoch Affiliation(s): School of Engineering and Information Technology
Publisher: IOS Press
Item Control Page Item Control Page