Minimal Circular Strings


The Transactions of the Korea Information Processing Society (1994 ~ 2000), Vol. 5, No. 9, pp. 2415-2420, Sep. 1998
10.3745/KIPSTE.1998.5.9.2415,   PDF Download:

Abstract

We present a linear time algorithm for finding a lexicographically minimal circular string in a given string. The problem was motivated by an effort to implement state transition functions in isotropic cellular automata. A native algorithm for the problem would require quadratic time. The proposed algorithm runs in linear time by keeping the result of comparisons of substrings and reusing it afterwards when the same computation is needed.


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]
W. K. Bum and Y. H. Jin, "Minimal Circular Strings," The Transactions of the Korea Information Processing Society (1994 ~ 2000), vol. 5, no. 9, pp. 2415-2420, 1998. DOI: 10.3745/KIPSTE.1998.5.9.2415.

[ACM Style]
Wee Kyun Bum and Yeh Hong Jin. 1998. Minimal Circular Strings. The Transactions of the Korea Information Processing Society (1994 ~ 2000), 5, 9, (1998), 2415-2420. DOI: 10.3745/KIPSTE.1998.5.9.2415.