Lyndon 인수분해¶
Lyndon 인수분해¶
먼저 Lyndon 인수분해의 개념을 정의합시다.
어떤 문자열이 자기 자신의 자명하지 않은 모든 접미사보다 엄격하게 작으면, 그 문자열을 단순(simple) 문자열(또는 Lyndon 단어)이라고 합니다. 단순 문자열의 예로는 $a$, $b$, $ab$, $aab$, $abb$, $ababb$, $abcd$가 있습니다. 어떤 문자열이 단순 문자열이라는 것은 그 문자열이 자기 자신의 자명하지 않은 모든 순환 이동보다 엄격하게 작다는 것과 동치임을 보일 수 있습니다.
다음으로, 문자열 $s$가 주어졌다고 합시다. 문자열 $s$의 Lyndon 인수분해는 $s = w_1 w_2 \dots w_k$ 형태의 인수분해로, 모든 문자열 $w_i$는 단순 문자열이며 비증가 순서 $w_1 \ge w_2 \ge \dots \ge w_k$를 이룹니다.
어떤 문자열에 대해서도 이러한 인수분해가 존재하며 유일하다는 것을 보일 수 있습니다.
Duval 알고리즘¶
Duval 알고리즘은 $O(1)$의 추가 메모리를 사용하여 $O(n)$ 시간에 Lyndon 인수분해를 구성합니다.
먼저 또 다른 개념을 도입합시다: 문자열 $t$가 $t = w w \dots w \overline{w}$ 형태이고, 여기서 $w$가 단순 문자열이며 $\overline{w}$가 $w$의 접두사(빈 문자열일 수도 있음)이면, $t$를 준단순(pre-simple) 문자열이라고 합니다. 단순 문자열은 준단순 문자열이기도 합니다.
Duval 알고리즘은 그리디 알고리즘입니다. 실행 중 어느 시점에서든 문자열 $s$는 실제로 세 문자열 $s = s_1 s_2 s_3$로 나뉘어 있습니다. 여기서 $s_1$에 대한 Lyndon 인수분해는 이미 구해져 확정되었고, 문자열 $s_2$는 준단순 문자열이며(그 안에 있는 단순 문자열의 길이도 알고 있습니다), $s_3$은 전혀 건드리지 않은 상태입니다. 각 반복에서 Duval 알고리즘은 문자열 $s_3$의 첫 번째 문자를 가져와 문자열 $s_2$에 덧붙이려고 시도합니다. $s_2$가 더 이상 준단순 문자열이 아니게 되면 $s_2$의 일부분에 대한 Lyndon 인수분해가 알려지고, 그 부분은 $s_1$으로 넘어갑니다.
알고리즘을 좀 더 자세히 설명하겠습니다. 포인터 $i$는 항상 문자열 $s_2$의 시작을 가리킵니다. 바깥쪽 루프는 $i < n$인 동안 실행됩니다. 루프 안에서는 두 개의 추가 포인터를 사용하는데, $j$는 $s_3$의 시작을 가리키고, $k$는 현재 비교 대상인 문자를 가리킵니다. 문자 $s[j]$를 문자열 $s_2$에 추가하려고 하며, 이를 위해서는 문자 $s[k]$와 비교해야 합니다. 다음과 같은 세 가지 경우가 있을 수 있습니다:
- $s[j] = s[k]$: 이 경우에는 기호 $s[j]$를 $s_2$에 추가해도 준단순성이 깨지지 않습니다. 따라서 포인터 $j$와 $k$를 단순히 1씩 증가시킵니다.
- $s[j] > s[k]$: 이 경우 문자열 $s_2 + s[j]$는 단순 문자열이 됩니다. $j$를 1 증가시키고 $k$를 다시 $s_2$의 시작으로 되돌려서, 다음 문자가 단순 단어의 시작 부분과 비교되도록 할 수 있습니다.
- $s[j] < s[k]$: 문자열 $s_2 + s[j]$는 더 이상 준단순 문자열이 아닙니다. 따라서 준단순 문자열 $s_2$를 그 안의 단순 문자열들과 나머지(빈 문자열일 수도 있음)로 분리합니다. 단순 문자열의 길이는 $j - k$입니다. 다음 반복에서는 남은 $s_2$로 다시 시작합니다.
구현¶
다음은 주어진 문자열 $s$에 대해 원하는 Lyndon 인수분해를 반환하는 Duval 알고리즘의 구현입니다.
vector<string> duval(string const& s) {
int n = s.size();
int i = 0;
vector<string> factorization;
while (i < n) {
int j = i + 1, k = i;
while (j < n && s[k] <= s[j]) {
if (s[k] < s[j])
k = i;
else
k++;
j++;
}
while (i <= k) {
factorization.push_back(s.substr(i, j - k));
i += j - k;
}
}
return factorization;
}
복잡도¶
이 알고리즘의 실행 시간을 추정해 봅시다.
바깥쪽 while 루프는 매 반복이 끝날 때마다 $i$가 증가하므로 $n$번을 넘게 반복하지 않습니다. 또한 두 번째 내부 while 루프는 최종 인수분해를 출력하기만 하므로 $O(n)$에 실행됩니다.
따라서 우리가 관심을 가질 것은 첫 번째 안쪽 while 루프뿐입니다. 최악의 경우 이 루프는 몇 번 반복합니까? 바깥쪽 루프의 각 반복에서 찾아내는 단순 단어가 추가로 비교한 나머지 부분보다 길다는 것은 쉽게 알 수 있습니다. 따라서 나머지 부분들의 합 역시 $n$보다 작으며, 이는 첫 번째 안쪽 while 루프를 최대 $O(n)$번만 반복한다는 뜻입니다. 실제로 문자 비교의 총 횟수는 $4n - 3$을 넘지 않습니다.
가장 작은 순환 이동 찾기¶
문자열 $s$가 있다고 합시다. 문자열 $s + s$에 대한 Lyndon 인수분해를 ($O(n)$ 시간에) 구성합니다. 인수분해에서 $n$보다 작은 위치에서 시작하고(즉, $s$의 첫 번째 사본에서 시작하고), $n$ 이상인 위치에서 끝나는(즉, $s$의 두 번째 사본에서 끝나는) 단순 문자열을 찾습니다. 이 단순 문자열의 시작 위치가 곧 원하는 가장 작은 순환 이동의 시작점이 된다고 알려져 있습니다. 이는 Lyndon 분해의 정의를 이용하면 쉽게 확인할 수 있습니다.
단순 블록의 시작점은 쉽게 찾을 수 있습니다. 바깥쪽 루프의 각 반복이 시작될 때 현재 준단순 문자열의 시작을 가리키는 포인터 $i$를 기억해 두기만 하면 됩니다.
따라서 다음과 같은 구현을 얻습니다.
string min_cyclic_string(string s) {
s += s;
int n = s.size();
int i = 0, ans = 0;
while (i < n / 2) {
ans = i;
int j = i + 1, k = i;
while (j < n && s[k] <= s[j]) {
if (s[k] < s[j])
k = i;
else
k++;
j++;
}
while (i <= k)
i += j - k;
}
return s.substr(ans, n / 2);
}