Minimal Circular Strings 


Vol. 5,  No. 9, pp. 2415-2420, Sep.  1998
10.3745/KIPSTE.1998.5.9.2415


PDF
  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
  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.

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