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


The KIPS Transactions:PartA, Vol. 15, No. 4, pp. 239-242, Aug. 2008
10.3745/KIPSTA.2008.15.4.239,   PDF Download:

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
Show / Hide Statistics

Statistics (Cumulative Counts from September 1st, 2017)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.


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.