Efficient External Memory Algorithm for Finding the Maximum Suffix of a String 


Vol. 15,  No. 4, pp. 239-242, Aug.  2008
10.3745/KIPSTA.2008.15.4.239


PDF
  Abstract

We study the problem of finding the maximum suffix of a string on the external memory model of computation with one disk. In this model, we are primarily interested in designing algorithms that reduce the number of I/Os between the disk and the internal memory. A string of length has suffixes and among these, the lexicographically largest one is called the maximum suffix of the string. Finding the maximum suffix of a string plays a crucial role in solving some string problems. In this paper, we present an external memory algorithm for computing the maximum suffix of a string of length. The algorithm uses four blocks in the internal memory and performs at most 4 disk I/Os, where is the size of a block.

  Statistics
  Cite this article

[IEEE Style]

S. K. Kim, S. C. Kim, J. S. Cho, "Efficient External Memory Algorithm for Finding the Maximum Suffix of a String," The KIPS Transactions:PartA, vol. 15, no. 4, pp. 239-242, 2008. DOI: 10.3745/KIPSTA.2008.15.4.239.

[ACM Style]

Sung Kwon Kim, Soo Cheol Kim, and Jung Sik Cho. 2008. Efficient External Memory Algorithm for Finding the Maximum Suffix of a String. The KIPS Transactions:PartA, 15, 4, (2008), 239-242. DOI: 10.3745/KIPSTA.2008.15.4.239.

Forms

Search
(IN TITLE, AUTHOR, ABSTRACT,KEYWORDS)

Advanced Search ▼

POPULAR KEYWORDS
(TOP 10 KEYWORDS)

Recent Publications
(LAST 3 YEARS)

Old Journals

Indexing

All publications of TKIPS is indexed in DOI, EBSCO, Google Scholar, Crossref, and CrossCheck.

TKIPS is also selected as the Journal for Accreditation by NRF (National Research Foundation of Korea).

Related Journals