- 최소 원형 스트링
- Minimal Circular Strings
- ㆍ 저자명
- 위규범,예홍진,Wee. Kyu-Bum,Yeh. Hong-Jin
- ㆍ 간행물명
- 정보처리논문지
- ㆍ 권/호정보
- 1998년|5권 9호|pp.2415-2420 (6 pages)
- ㆍ 발행정보
- 한국정보처리학회
- ㆍ 파일정보
- 정기간행물| PDF텍스트
- ㆍ 주제분야
- 기타
이 논문은 한국과학기술정보연구원과 논문 연계를 통해 무료로 제공되는 원문입니다.
주어진 문자열을 환형 이동한 문자열들 중에서 사전적 순서로 가장 작은 것을 찾는 선형 시간 알고리즘을 제시한다. 이 문제는 등방성의 셀룰러 오토마타의 상태전이함수의 효율적인 구현에서 생긴다. 이 문제에 대한 단순한 알고리즘은 이차시간을 필요로 한다. 본 논문에서 제안하는 알고리즘은 부분스트링들의 비교 결과를 저장하고 나중에 같은 계산이 필요한 경우에 저장한 결과를 다시 사용함으로서 선형시간에 문제를 해결한다.
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 artomata. A naive algorthm 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 agterwards when the same computation is needed.