반복 찾기¶

길이가 $n$인 문자열 $s$가 주어집니다.

반복이란 어떤 문자열이 두 번 연달아 나타나는 것을 말합니다. 다시 말해, 반복은 부분 문자열 $s[i \dots j]$가 동일한 두 문자열을 이어 쓴 형태가 되도록 하는 인덱스 쌍 $i < j$로 나타낼 수 있습니다.

과제는 주어진 문자열 $s$에서 모든 반복을 찾는 것입니다. 또는 더 단순한 과제로, 아무 반복이나 하나 찾거나 가장 긴 반복을 찾을 수도 있습니다.

여기서 설명하는 알고리즘은 1982년에 Main과 Lorentz가 발표했습니다.

예시¶

다음 예시 문자열에서 반복을 살펴봅시다.

$$acababaee$$

이 문자열에는 다음 세 개의 반복이 있습니다.

$s[2 \dots 5] = abab$
$s[3 \dots 6] = baba$
$s[7 \dots 8] = ee$

또 다른 예시입니다.

$$abaaba$$

여기에는 반복이 두 개뿐입니다.

$s[0 \dots 5] = abaaba$
$s[2 \dots 3] = aa$

반복의 개수¶

일반적으로 길이가 $n$인 문자열에는 반복이 최대 $O(n^2)$개까지 있을 수 있습니다. 명백한 예로 같은 문자를 $n$번 나열한 문자열이 있으며, 이 경우 길이가 짝수인 모든 부분 문자열이 반복입니다. 일반적으로 주기가 짧은 주기적 문자열에는 반복이 많이 포함됩니다.

한편 이 사실 때문에 반복의 개수를 $O(n \log n)$ 시간에 계산하지 못하는 것은 아닙니다. 알고리즘이 반복을 압축된 형태로, 즉 여러 개를 한꺼번에 묶은 그룹으로 제공할 수 있기 때문입니다.

심지어 주기적 부분 문자열의 그룹을 크기가 4인 튜플로 나타내는 개념도 있습니다. 이러한 그룹의 개수는 문자열 길이에 대해 많아야 선형임이 증명되어 있습니다.

또한 반복의 개수와 관련된 흥미로운 결과를 몇 가지 더 소개합니다.

원시 반복(절반이 반복이 아닌 반복)의 개수는 최대 $O(n \log n)$입니다.
반복을 수의 튜플(Crochemore 삼중쌍이라고 부릅니다) $(i,~ p,~ r)$로 인코딩하면(여기서 $i$는 시작 위치, $p$는 반복되는 부분 문자열의 길이, $r$은 반복 횟수입니다), 모든 반복을 이러한 삼중쌍 $O(n \log n)$개로 나타낼 수 있습니다.
다음과 같이 정의되는 피보나치 문자열은

$$\begin{align} t_0 &= a, \\\\ t_1 &= b, \\\\ t_i &= t_{i-1} + t_{i-2}, \end{align}$$

"강하게" 주기적입니다. 피보나치 문자열 $f_i$에서 반복의 개수는 Crochemore 삼중쌍으로 압축하더라도 $O(f_n \log f_n)$입니다. 원시 반복의 개수 역시 $O(f_n \log f_n)$입니다.

Main-Lorentz 알고리즘¶

Main-Lorentz 알고리즘의 핵심 아이디어는 분할 정복입니다.

이 알고리즘은 처음 문자열을 절반으로 나누고, 두 번의 재귀 호출로 각 절반 안에 완전히 들어 있는 반복의 개수를 계산합니다. 그다음이 어려운 부분입니다. 알고리즘은 앞쪽 절반에서 시작하여 뒤쪽 절반에서 끝나는 모든 반복(이를 교차 반복이라고 부르겠습니다)을 찾습니다. 이것이 Main-Lorentz 알고리즘의 핵심 부분이며, 여기서 자세히 설명하겠습니다.

분할 정복 알고리즘의 복잡도는 이미 잘 연구되어 있습니다. 마스터 정리에 따르면, 교차 반복을 $O(n)$ 시간에 계산할 수 있다면 최종적으로 $O(n \log n)$ 알고리즘을 얻게 됩니다.

교차 반복 찾기¶

따라서 문자열의 앞쪽 절반(이를 $u$라고 부릅시다)에서 시작하여 뒤쪽 절반(이를 $v$라고 부릅시다)에서 끝나는 모든 반복을 찾고자 합니다:

$$s = u + v$$

이들의 길이는 대략 $s$의 길이를 2로 나눈 값과 같습니다.

임의의 반복을 하나 잡고 가운데 문자(더 정확히는 반복의 뒤쪽 절반의 첫 번째 문자)를 살펴봅시다. 즉, 반복이 부분 문자열 $s[i \dots j]$라면 가운데 문자는 $(i + j + 1) / 2$입니다.

이 문자가 문자열 $u$와 문자열 $v$ 중 어디에 위치하는지에 따라 반복을 왼쪽 반복 또는 오른쪽 반복이라고 부릅니다. 다시 말해, 문자열의 대부분이 $u$에 놓여 있으면 왼쪽이라고 부르고, 그렇지 않으면 오른쪽이라고 부릅니다.

이제 모든 왼쪽 반복을 찾는 방법을 살펴보겠습니다. 모든 오른쪽 반복도 같은 방법으로 찾을 수 있습니다.

왼쪽 반복의 길이를 $2l$로 나타냅시다(즉, 반복의 각 절반의 길이는 $l$입니다). 반복에서 문자열 $v$에 속하는 첫 번째 문자를 생각해 봅시다(이 문자는 문자열 $s$의 위치 $|u|$에 있습니다). 이 문자는 그보다 $l$칸 앞에 있는 문자와 일치하며, 이 위치를 $cntr$라고 합시다.

이 위치 $cntr$를 고정하고, $cntr$ 위치에서 모든 반복을 찾겠습니다.

예를 들면 다음과 같습니다:

$$c ~ \underset{cntr}{a} ~ c ~ | ~ a ~ d ~ a$$

세로선은 두 절반을 나눕니다. 여기서는 위치 $cntr = 1$을 고정했으며, 이 위치에서 반복 $caca$를 찾습니다.

위치 $cntr$를 고정하면 가능한 반복의 길이도 동시에 고정된다는 것은 분명합니다: $l = |u| - cntr$. 이러한 반복을 찾는 방법을 알게 되면, $cntr$의 가능한 모든 값을 $0$부터 $|u|-1$까지 순회하여 길이가 $l = |u|,~ |u|-1,~ \dots, 1$인 모든 왼쪽 교차 반복을 찾을 것입니다.

왼쪽 교차 반복의 판정 기준¶

그러면 고정된 $cntr$에 대해 이러한 반복을 모두 어떻게 찾을 수 있겠습니까? 이러한 반복이 여전히 여러 개 있을 수 있다는 점에 유의하십시오.

다시 시각화를 살펴봅시다. 이번에는 반복 $abcabc$에 대한 것입니다:

$$\overbrace{a}^{l_1} ~ \overbrace{\underset{cntr}{b} ~ c}^{l_2} ~ \overbrace{a}^{l_1} ~ | ~ \overbrace{b ~ c}^{l_2}$$

여기서 반복의 두 조각의 길이를 $l_1$과 $l_2$로 나타냈습니다: $l_1$은 위치 $cntr-1$까지의 반복의 길이이고, $l_2$는 $cntr$부터 반복의 절반이 끝나는 지점까지의 반복의 길이입니다. 반복의 전체 길이는 $2l = l_1 + l_2 + l_1 + l_2$입니다.

위치 $cntr$에서 길이가 $2l = 2(l_1 + l_2) = 2(|u| - cntr)$인 이러한 반복에 대한 필요충분 조건을 만들어 봅시다:

$k_1$을 위치 $cntr$ 앞의 $k_1$개 문자가 문자열 $u$의 마지막 $k_1$개 문자와 일치하는 가장 큰 수라고 합시다:

$$ u[cntr - k_1 \dots cntr - 1] = u[|u| - k_1 \dots |u| - 1] $$

$k_2$를 위치 $cntr$에서 시작하는 $k_2$개 문자가 문자열 $v$의 처음 $k_2$개 문자와 일치하는 가장 큰 수라고 합시다:

$$ u[cntr \dots cntr + k_2 - 1] = v[0 \dots k_2 - 1] $$

그러면 다음을 만족하는 쌍 $(l_1,~ l_2)$에 대해서, 그리고 오직 그러한 쌍에 대해서만 반복이 존재합니다

$$ \begin{align} l_1 &\le k_1, \\\\ l_2 &\le k_2. \\\\ \end{align} $$

요약하면 다음과 같습니다:

특정 위치 $cntr$를 고정합니다.
이제 찾을 모든 반복의 길이는 $2l = 2(|u| - cntr)$입니다. 이러한 반복은 여러 개 있을 수 있으며, 이들은 길이 $l_1$과 $l_2 = l - l_1$에 따라 달라집니다.
위에서 설명한 대로 $k_1$과 $k_2$를 구합니다.
그러면 조각의 길이 $l_1$과 $l_2$가 다음 조건을 만족하는 반복이 모두 적합한 반복입니다:

$$ \begin{align} l_1 + l_2 &= l = |u| - cntr \\\\ l_1 &\le k_1, \\\\ l_2 &\le k_2. \\\\ \end{align} $$

따라서 남은 부분은 모든 위치 $cntr$에 대해 값 $k_1$과 $k_2$를 어떻게 빠르게 계산하는지뿐입니다. 다행히 Z-함수를 사용하면 이 값들을 $O(1)$에 계산할 수 있습니다:

문자열 $\overline{u}$(즉, 문자열 $u$를 뒤집은 문자열)에 대한 Z-함수를 계산하면 각 위치의 값 $k_1$을 구할 수 있습니다. 그러면 특정 $cntr$에 대한 값 $k_1$은 Z-함수 배열의 해당 값과 같습니다.
모든 $k_2$ 값을 미리 계산하기 위해 문자열 $v + \# + u$(즉, 문자열 $u$에 구분 문자 $\#$와 문자열 $v$를 이어 붙인 문자열)에 대한 Z-함수를 계산합니다. 이번에도 Z-함수에서 해당 값을 찾아보기만 하면 $k_2$ 값을 얻을 수 있습니다.

이것으로 모든 왼쪽 교차 반복을 찾기에 충분합니다.

오른쪽 교차 반복¶

오른쪽 교차 반복을 계산할 때도 비슷하게 진행합니다: 중심 $cntr$를 문자열 $u$의 마지막 문자에 대응하는 문자로 정의합니다.

그러면 길이 $k_1$은 위치 $cntr$ 이전(해당 위치 포함)의 문자 중 문자열 $u$의 마지막 문자들과 일치하는 문자의 최대 개수로 정의됩니다. 그리고 길이 $k_2$는 $cntr + 1$부터 시작하는 문자 중 문자열 $v$의 문자들과 일치하는 문자의 최대 개수로 정의됩니다.

따라서 문자열 $\overline{u} + \# + \overline{v}$와 $v$에 대한 Z-함수를 계산하면 값 $k_1$과 $k_2$를 구할 수 있습니다.

그런 다음 모든 위치 $cntr$를 살펴보며 왼쪽 교차 반복에서와 같은 기준을 사용하면 반복을 찾을 수 있습니다.

구현¶

Main-Lorentz 알고리즘의 구현은 모든 반복을 크기가 4인 특수한 튜플 $(cntr,~ l,~ k_1,~ k_2)$의 형태로 $O(n \log n)$ 시간에 찾습니다. 문자열에 있는 반복의 개수만 구하거나 문자열에서 가장 긴 반복만 찾으려는 경우에는 이 정보로 충분하며, 실행 시간은 여전히 $O(n \log n)$입니다.

이 튜플들을 펼쳐서 각 반복의 시작 위치와 끝 위치를 얻으려면 실행 시간이 $O(n^2)$이 된다는 점에 유의하십시오(반복이 $O(n^2)$개까지 있을 수 있다는 점을 기억하십시오). 이 구현에서는 그렇게 하여, 찾은 모든 반복을 시작 인덱스와 끝 인덱스 쌍의 벡터에 저장합니다.

vector<int> z_function(string const& s) {
    int n = s.size();
    vector<int> z(n);
    for (int i = 1, l = 0, r = 0; i < n; i++) {
        if (i <= r)
            z[i] = min(r-i+1, z[i-l]);
        while (i + z[i] < n && s[z[i]] == s[i+z[i]])
            z[i]++;
        if (i + z[i] - 1 > r) {
            l = i;
            r = i + z[i] - 1;
        }
    }
    return z;
}

int get_z(vector<int> const& z, int i) {
    if (0 <= i && i < (int)z.size())
        return z[i];
    else
        return 0;
}

vector<pair<int, int>> repetitions;

void convert_to_repetitions(int shift, bool left, int cntr, int l, int k1, int k2) {
    for (int l1 = max(1, l - k2); l1 <= min(l, k1); l1++) {
        if (left && l1 == l) break;
        int l2 = l - l1;
        int pos = shift + (left ? cntr - l1 : cntr - l - l1 + 1);
        repetitions.emplace_back(pos, pos + 2*l - 1);
    }
}

void find_repetitions(string s, int shift = 0) {
    int n = s.size();
    if (n == 1)
        return;

    int nu = n / 2;
    int nv = n - nu;
    string u = s.substr(0, nu);
    string v = s.substr(nu);
    string ru(u.rbegin(), u.rend());
    string rv(v.rbegin(), v.rend());

    find_repetitions(u, shift);
    find_repetitions(v, shift + nu);

    vector<int> z1 = z_function(ru);
    vector<int> z2 = z_function(v + '#' + u);
    vector<int> z3 = z_function(ru + '#' + rv);
    vector<int> z4 = z_function(v);

    for (int cntr = 0; cntr < n; cntr++) {
        int l, k1, k2;
        if (cntr < nu) {
            l = nu - cntr;
            k1 = get_z(z1, nu - cntr);
            k2 = get_z(z2, nv + 1 + cntr);
        } else {
            l = cntr - nu + 1;
            k1 = get_z(z3, nu + 1 + nv - 1 - (cntr - nu));
            k2 = get_z(z4, (cntr - nu) + 1);
        }
        if (k1 + k2 >= l)
            convert_to_repetitions(shift, cntr < nu, cntr, l, k1, k2);
    }
}