린던 분해·최소 회전 계산기
문자열을 사전순 비증가하는 린던 워드들의 곱으로 쪼개는 두발 알고리즘을 단계별로 보여 줍니다. 같은 알고리즘을 두 번 이어 붙인 문자열에 돌리면 사전순 최소 회전이 공짜로 나옵니다.
200자까지. 사전순은 문자 코드 순서로 봅니다.
린던 분해
b · an · an · a
조각 4개로 쪼개졌습니다. 사전순 비증가로 늘어서며, 이렇게 쪼개는 방법은 하나뿐입니다.
조각마다
| # | 조각 | 시작 | 길이 | 린던 워드인가 |
|---|---|---|---|---|
| 1 | b | 1 | 1 | 예 |
| 2 | an | 2 | 2 | 예 |
| 3 | an | 4 | 2 | 예 |
| 4 | a | 6 | 1 | 예 |
사전순 최소 회전
참고
두발 알고리즘이 움직인 과정
| i | j | k | 비교 | 한 일 |
|---|---|---|---|---|
| 0 | 1 | 0 | s[k] > s[j] | 조각 떼어냄: b |
| 1 | 2 | 1 | s[k] < s[j] | k를 i로 되돌리고 j++ |
| 1 | 3 | 1 | s[k] = s[j] | k++, j++ (주기가 이어짐) |
| 1 | 4 | 2 | s[k] = s[j] | k++, j++ (주기가 이어짐) |
| 1 | 5 | 3 | s[k] = s[j] | k++, j++ (주기가 이어짐) |
| 1 | 6 | 4 | s[k] > s[j] | 조각 떼어냄: an · an |
| 5 | 6 | 5 | s[k] > s[j] | 조각 떼어냄: a |
사용 방법
- 1문자열을 넣습니다. 알파벳은 무엇이든 되고 사전순은 문자 코드 순서로 봅니다.
- 2린던 분해 결과와 각 조각의 시작 위치가 나옵니다.
- 3포인터 i·j·k가 어떻게 움직였는지 단계별로 확인합니다.
- 4사전순 최소 회전과 그 시작 위치도 함께 나옵니다.
- 5회전을 모두 만들어 고른 결과와 나란히 놓아 검산합니다.
자주 묻는 질문
자기 자신의 모든 진회전보다 사전순으로 앞선 문자열입니다. "aab"은 회전 "aba"·"baa"가 모두 뒤에 오므로 린던 워드이고, "aba"는 회전 "aab"이 앞에 오므로 아닙니다. 여기서 따라 나오는 중요한 성질이 하나 있는데, 린던 워드는 주기를 가질 수 없다는 것입니다 — "abab"은 자기 회전과 같아지므로 탈락합니다.
그렇습니다. 슈발레–팽–린던 정리가 «모든 문자열은 사전순 비증가하는 린던 워드들의 곱으로 유일하게 쪼개진다»고 말합니다. "banana"를 b·an·an·a가 아닌 다른 방식으로 쪼개려 하면 어느 조각이 린던 워드가 아니거나 비증가 조건이 깨집니다. 유일성이 이 분해의 값어치입니다.
문자열을 두 번 이어 붙이면 모든 회전이 그 안에 부분문자열로 들어 있기 때문입니다. s+s에 두발 알고리즘을 돌려 길이 n을 처음 넘어서는 조각의 시작 위치가 곧 최소 회전의 시작점입니다. 부스(Booth) 알고리즘과 결과가 같고 구현이 훨씬 짧습니다.
방향이 반대입니다. 드 브루인 쪽은 린던 워드들을 «만들어 이어 붙여» 수열을 짓고, 이 계산기는 주어진 문자열을 «쪼갭니다». 같은 정리를 양쪽에서 쓰는 셈이라 함께 보시면 린던 워드가 왜 유용한지 보입니다.
전송되지 않습니다. 모든 계산은 브라우저 안에서만 이뤄지고, 입력값은 이 기기의 저장소에만 남습니다.
알아두면 좋은 점
- 사전순은 자바스크립트의 문자열 비교(UTF-16 코드 단위 순서)를 따릅니다. 한글·이모지처럼 코드가 큰 문자도 넣을 수 있지만 «가나다순»과는 다를 수 있습니다.
- 두발 알고리즘 자체는 O(n) 시간·O(1) 추가 공간이지만, 이 계산기는 과정을 보여 주려고 단계를 모두 기록합니다.
- 길이 200자까지 다룹니다.
- 무작위 문자열 3000개에서 조각마다 정의대로 린던 워드인지, 비증가인지 확인했고 최소 회전은 회전 전체를 만들어 대조했습니다.
함께 보면 좋은 도구
마지막 검증: 2026년 9월 2일 · 결과는 참고용 추정치입니다.