Affiliations: School of Computer Science and Engineering, Seoul
National University, Seoul, Korea. E-mail: {khroh,kpark}@theory.snu.ac.kr | Dept. of Computer Sciences, King's College London, UK
and Université Paris-Est, France. E-mail:
[email protected] | Department of Computer Sciences, King's College
London, London, United Kingdom. E-mail: [email protected]
Abstract: In this paper we present external memory algorithms for some string
problems. External memory algorithms have been developed in many research
areas, as the speed gap between fast internal memory and slow external memory
continues to grow. The goal of external memory algorithms is to minimize the
number of input/output operations between internal memory and external
memory. These years the sizes of strings such as DNA sequences are rapidly
increasing. However, external memory algorithms have been developed for only a
few string problems. In this paper we consider five string problems and present
external memory algorithms for them. They are the problems of finding the
maximum suffix, string matching, period finding, Lyndon decomposition, and
finding the minimum of a circular string. Every algorithm that we present here
runs in a linear number of I/Os in the external memory model with one disk, and
they run in an optimal number of disk I/Os in the external memory model with
multiple disks.
Keywords: Externalmemory algorithm, maximum suffix, string matching, period finding, Lyndon decomposition, minimum of a circular string
