접미사 배열¶

정의¶

$s$를 길이가 $n$인 문자열이라고 합시다. $s$의 $i$번째 접미사는 부분 문자열 $s[i \ldots n - 1]$입니다.

접미사 배열은 주어진 문자열의 모든 접미사를 정렬한 뒤, 그 접미사들의 시작 인덱스를 나타내는 정수들을 담습니다.

예시로 문자열 $s = abaab$를 살펴봅시다. 모든 접미사는 다음과 같습니다.

$$\begin{array}{ll} 0. & abaab \\ 1. & baab \\ 2. & aab \\ 3. & ab \\ 4. & b \end{array}$$

이 문자열들을 정렬하면 다음과 같습니다:

$$\begin{array}{ll} 2. & aab \\ 3. & ab \\ 0. & abaab \\ 4. & b \\ 1. & baab \end{array}$$

따라서 $s$의 접미사 배열은 $(2,~ 3,~ 0,~ 4,~ 1)$입니다.

접미사 배열은 자료 구조로서 데이터 압축, 생물정보학을 비롯하여 일반적으로 문자열과 문자열 매칭 문제를 다루는 모든 분야에서 널리 사용됩니다.

구성¶

$O(n^2 \log n)$ 접근법¶

이것은 가장 단순한 접근법입니다. 모든 접미사를 구한 뒤 퀵 정렬이나 병합 정렬로 정렬하면서, 동시에 각 접미사의 원래 인덱스를 유지합니다. 정렬에는 $O(n \log n)$번의 비교가 필요하고, 두 문자열을 비교하는 데 추가로 $O(n)$ 시간이 걸리므로 최종 복잡도는 $O(n^2 \log n)$입니다.

$O(n \log n)$ 접근법¶

엄밀히 말하면 다음 알고리즘은 접미사를 정렬하는 것이 아니라 문자열의 순환 이동을 정렬합니다. 하지만 이로부터 접미사를 정렬하는 알고리즘을 매우 쉽게 얻을 수 있습니다: 문자열에 있는 어떤 문자보다도 작은 임의의 문자를 문자열 끝에 덧붙이기만 하면 됩니다. 보통 기호 $를 사용합니다. 그러면 정렬된 순환 이동의 순서는 정렬된 접미사의 순서와 동일하며, 이는 문자열 $dabbb$로 여기에서 보인 바와 같습니다.

$$\begin{array}{lll} 1. & abbb\$d & abbb \\ 4. & b\$dabb & b \\ 3. & bb\$dab & bb \\ 2. & bbb\$da & bbb \\ 0. & dabbb\$ & dabbb \end{array}$$

순환 이동을 정렬할 것이므로 순환 부분 문자열을 고려하겠습니다. $i > j$인 경우에도 $s$의 부분 문자열을 $s[i \dots j]$로 표기하겠습니다. 이 경우 실제로는 문자열 $s[i \dots n-1] + s[0 \dots j]$를 의미합니다. 또한 모든 인덱스는 $s$의 길이로 나눈 나머지로 취하며, 간결함을 위해 나머지 연산은 생략하겠습니다.

여기서 다루는 알고리즘은 $\lceil \log n \rceil + 1$번의 반복을 수행합니다. $k$번째 반복($k = 0 \dots \lceil \log n \rceil$)에서는 길이가 $2^k$인 $s$의 순환 부분 문자열 $n$개를 정렬합니다. $\lceil \log n \rceil$번째 반복이 끝나면 길이가 $2^{\lceil \log n \rceil} \ge n$인 부분 문자열이 정렬되므로, 이는 순환 이동 전체를 정렬하는 것과 동일합니다.

알고리즘의 각 반복에서는 순열 $p[0 \dots n-1]$과 함께 배열 $c[0 \dots n-1]$도 유지합니다. 여기서 $p[i]$는 정렬된 순서에서 $i$번째 부분 문자열($i$에서 시작하고 길이가 $2^k$인 부분 문자열)의 인덱스이고, $c[i]$는 그 부분 문자열이 속한 동치류에 해당합니다. 일부 부분 문자열은 서로 같을 수 있고, 알고리즘은 이들을 동등하게 다루어야 하기 때문입니다. 편의상 각 클래스에는 0부터 시작하는 번호를 붙입니다. 또한 $c[i]$ 값은 순서 정보를 보존하도록 부여합니다: 한 부분 문자열이 다른 부분 문자열보다 작다면 클래스 번호도 더 작아야 합니다. 동치류의 개수는 변수 $\text{classes}$에 저장합니다.

예제를 살펴봅시다. 문자열 $s = aaba$를 생각해 봅시다. 각 반복의 순환 부분 문자열과 그에 해당하는 배열 $p[]$와 $c[]$는 다음과 같습니다:

$$\begin{array}{cccc} 0: & (a,~ a,~ b,~ a) & p = (0,~ 1,~ 3,~ 2) & c = (0,~ 0,~ 1,~ 0)\\ 1: & (aa,~ ab,~ ba,~ aa) & p = (0,~ 3,~ 1,~ 2) & c = (0,~ 1,~ 2,~ 0)\\ 2: & (aaba,~ abaa,~ baaa,~ aaab) & p = (3,~ 0,~ 1,~ 2) & c = (1,~ 2,~ 3,~ 0)\\ \end{array}$$

$p[]$의 값은 달라질 수 있다는 점에 주목할 필요가 있습니다. 예를 들어 $0$번째 반복에서 배열은 $p = (3,~ 1,~ 0,~ 2)$ 또는 $p = (3,~ 0,~ 1,~ 2)$일 수도 있습니다. 이 선택지들은 모두 부분 문자열을 정렬된 순서로 배열합니다. 따라서 모두 올바릅니다. 반면 배열 $c[]$는 하나로 정해지므로 모호함이 생길 수 없습니다.

이제 알고리즘의 구현을 살펴봅시다. 문자열 $s$를 받아 정렬된 순환 이동의 순열을 반환하는 함수를 작성하겠습니다.

vector<int> sort_cyclic_shifts(string const& s) {
    int n = s.size();
    const int alphabet = 256;

처음($0$번째 반복)에는 길이가 $1$인 순환 부분 문자열을 정렬해야 합니다. 즉, 문자열의 모든 문자를 정렬하고 동치류로 나누어야 합니다(같은 문자는 같은 클래스에 배정됩니다). 이는 예를 들어 계수 정렬을 사용하면 간단히 할 수 있습니다. 각 문자가 문자열에 몇 번 나타나는지 센 다음, 이 정보로 배열 $p[]$를 만듭니다. 그다음 배열 $p[]$를 순회하며 인접한 문자를 비교해 $c[]$를 구성합니다.

    vector<int> p(n), c(n), cnt(max(alphabet, n), 0);
    for (int i = 0; i < n; i++)
        cnt[s[i]]++;
    for (int i = 1; i < alphabet; i++)
        cnt[i] += cnt[i-1];
    for (int i = 0; i < n; i++)
        p[--cnt[s[i]]] = i;
    c[p[0]] = 0;
    int classes = 1;
    for (int i = 1; i < n; i++) {
        if (s[p[i]] != s[p[i-1]])
            classes++;
        c[p[i]] = classes - 1;
    }

이제 반복 단계를 설명하겠습니다. 이미 $k-1$번째 단계를 수행하여 그 단계의 배열 $p[]$와 $c[]$ 값을 계산했다고 가정합시다. $k$번째 단계의 값은 $O(n)$ 시간에 계산하고자 합니다. 이 단계를 $O(\log n)$번 수행하므로 전체 알고리즘의 시간 복잡도는 $O(n \log n)$이 됩니다.

이를 위해, 길이가 $2^k$인 순환 부분 문자열은 길이가 $2^{k-1}$인 부분 문자열 두 개로 이루어진다는 점에 주목하십시오. 이 두 부분 문자열은 이전 단계의 정보, 즉 동치류 값 $c[]$를 이용해 $O(1)$에 서로 비교할 수 있습니다. 따라서 위치 $i$와 $j$에서 시작하는 길이 $2^k$의 두 부분 문자열을 비교하는 데 필요한 정보는 모두 쌍 $(c[i],~ c[i + 2^{k-1}])$과 $(c[j],~ c[j + 2^{k-1}])$에 들어 있습니다.

$$\dots \overbrace{ \underbrace{s_i \dots s_{i+2^{k-1}-1}}_{\text{length} = 2^{k-1},~ \text{class} = c[i]} \quad \underbrace{s_{i+2^{k-1}} \dots s_{i+2^k-1}}_{\text{length} = 2^{k-1},~ \text{class} = c[i + 2^{k-1}]} }^{\text{length} = 2^k} \dots \overbrace{ \underbrace{s_j \dots s_{j+2^{k-1}-1}}_{\text{length} = 2^{k-1},~ \text{class} = c[j]} \quad \underbrace{s_{j+2^{k-1}} \dots s_{j+2^k-1}}_{\text{length} = 2^{k-1},~ \text{class} = c[j + 2^{k-1}]} }^{\text{length} = 2^k} \dots $$

이로부터 매우 간단한 해법을 얻습니다: 길이가 $2^k$인 부분 문자열을 이 수의 쌍을 기준으로 정렬합니다. 이렇게 하면 필요한 순서 $p[]$를 얻습니다. 그러나 일반적인 정렬은 $O(n \log n)$ 시간이 걸리므로 만족스럽지 않습니다. 이 방법으로는 $O(n \log^2 n)$ 시간에 접미사 배열을 구성하는 알고리즘밖에 얻을 수 없습니다.

이러한 쌍의 정렬을 어떻게 빠르게 수행할 수 있겠습니까? 쌍의 원소는 $n$을 넘지 않으므로 다시 계수 정렬을 사용할 수 있습니다. 그러나 계수 정렬로 쌍을 정렬하는 것은 가장 효율적인 방법이 아닙니다. 복잡도에 숨어 있는 상수를 더 줄이기 위해 다른 기법을 사용하겠습니다.

여기서는 기수 정렬의 기반이 되는 기법을 사용합니다: 쌍을 정렬하기 위해 먼저 두 번째 원소를 기준으로 정렬한 다음, 첫 번째 원소를 기준으로 정렬합니다(안정 정렬, 즉 같은 원소들의 상대적 순서를 깨뜨리지 않는 정렬을 사용합니다). 그런데 두 번째 원소들은 이전 반복에서 이미 정렬되어 있습니다. 따라서 쌍을 두 번째 원소를 기준으로 정렬하려면 $p[]$의 인덱스에서 $2^{k-1}$을 빼기만 하면 됩니다(예를 들어 길이가 $2^{k-1}$인 가장 작은 부분 문자열이 위치 $i$에서 시작한다면, 두 번째 절반이 가장 작은 길이 $2^k$의 부분 문자열은 $i - 2^{k-1}$에서 시작합니다).

그러므로 단순한 뺄셈만으로 $p[]$에 있는 쌍의 두 번째 원소를 정렬할 수 있습니다. 이제 첫 번째 원소를 기준으로 안정 정렬을 수행해야 합니다. 이미 언급했듯이 이는 계수 정렬로 수행할 수 있습니다.

남은 일은 동치류 $c[]$를 계산하는 것뿐인데, 이전과 마찬가지로 정렬된 순열 $p[]$를 순회하면서 이웃한 쌍을 비교하기만 하면 됩니다.

나머지 구현은 다음과 같습니다. 두 번째 원소 기준의 순열과 새로운 동치류 인덱스를 저장하기 위해 임시 배열 $pn[]$과 $cn[]$을 사용합니다.

    vector<int> pn(n), cn(n);
    for (int h = 0; (1 << h) < n; ++h) {
        for (int i = 0; i < n; i++) {
            pn[i] = p[i] - (1 << h);
            if (pn[i] < 0)
                pn[i] += n;
        }
        fill(cnt.begin(), cnt.begin() + classes, 0);
        for (int i = 0; i < n; i++)
            cnt[c[pn[i]]]++;
        for (int i = 1; i < classes; i++)
            cnt[i] += cnt[i-1];
        for (int i = n-1; i >= 0; i--)
            p[--cnt[c[pn[i]]]] = pn[i];
        cn[p[0]] = 0;
        classes = 1;
        for (int i = 1; i < n; i++) {
            pair<int, int> cur = {c[p[i]], c[(p[i] + (1 << h)) % n]};
            pair<int, int> prev = {c[p[i-1]], c[(p[i-1] + (1 << h)) % n]};
            if (cur != prev)
                ++classes;
            cn[p[i]] = classes - 1;
        }
        c.swap(cn);
    }
    return p;
}

이 알고리즘은 $O(n \log n)$ 시간과 $O(n)$ 메모리를 필요로 합니다. 간단하게 하기 위해 전체 ASCII 범위를 알파벳으로 사용했습니다.

문자열이 문자의 부분 집합만, 예를 들어 소문자만 포함한다는 것이 알려져 있다면 구현을 최적화할 수 있지만, 알파벳의 크기는 첫 번째 반복에서만 영향을 미치므로 최적화 효과는 미미할 가능성이 큽니다. 그 외의 모든 반복은 동치류의 개수에 좌우되며, 이 개수는 처음에 크기 $2$의 알파벳으로 이루어진 문자열이었더라도 빠르게 $O(n)$에 도달할 수 있습니다.

또한 이 알고리즘은 사이클 이동만 정렬한다는 점에 유의하십시오. 이 절의 시작 부분에서 언급했듯이, 문자열의 다른 모든 문자보다 작은 문자를 덧붙이고 그 결과 문자열을 사이클 이동으로 정렬하면, 예를 들어 $s + \$$의 사이클 이동을 정렬하면 접미사들의 정렬된 순서를 얻을 수 있습니다. 이렇게 하면 당연히 $s$의 접미사 배열을 얻지만, 그 앞에 $|s|$가 붙어 있습니다.

vector<int> suffix_array_construction(string s) {
    s += "$";
    vector<int> sorted_shifts = sort_cyclic_shifts(s);
    sorted_shifts.erase(sorted_shifts.begin());
    return sorted_shifts;
}

응용¶

가장 작은 순환 이동 찾기¶

위 알고리즘은 (문자열에 문자를 덧붙이지 않고) 모든 순환 이동을 정렬하므로, $p[0]$이 가장 작은 순환 이동의 위치를 알려 줍니다.

문자열에서 부분 문자열 찾기¶

이 문제는 어떤 텍스트 $t$ 안에서 문자열 $s$를 온라인으로 찾는 것입니다 - 텍스트 $t$는 미리 알고 있지만 문자열 $s$는 알지 못합니다. 텍스트 $t$에 대한 접미사 배열을 $O(|t| \log |t|)$ 시간에 만들 수 있습니다. 이제 다음과 같은 방법으로 부분 문자열 $s$를 찾을 수 있습니다. $s$의 등장은 반드시 $t$의 어떤 접미사의 접두사여야 합니다. 모든 접미사를 정렬했으므로 $p$에서 $s$에 대한 이진 탐색을 수행할 수 있습니다. 이진 탐색 중에 현재 접미사와 부분 문자열 $s$를 비교하는 것은 $O(|s|)$ 시간에 할 수 있으므로, 부분 문자열을 찾는 복잡도는 $O(|s| \log |t|)$입니다. 또한 부분 문자열이 $t$에 여러 번 등장한다면 모든 등장 위치가 $p$에서 서로 인접해 있다는 점에 주목하십시오. 따라서 등장 횟수는 두 번째 이진 탐색으로 구할 수 있으며, 모든 등장 위치도 쉽게 출력할 수 있습니다.

문자열의 두 부분 문자열 비교하기¶

주어진 문자열 $s$에서 길이가 같은 두 부분 문자열을 $O(1)$ 시간에 비교하려고 합니다. 즉, 첫 번째 부분 문자열이 두 번째 부분 문자열보다 작은지 확인하려고 합니다.

이를 위해 $O(|s| \log |s|)$ 시간에 접미사 배열을 구성하고, 동치류 $c[]$의 모든 중간 결과를 저장합니다.

이 정보를 이용하면 길이가 2의 거듭제곱인 임의의 두 부분 문자열을 O(1)에 비교할 수 있습니다. 이를 위해서는 두 부분 문자열의 동치류를 비교하는 것으로 충분합니다. 이제 이 방법을 임의의 길이를 가진 부분 문자열로 일반화하려고 합니다.

시작 인덱스가 $i$와 $j$이고 길이가 $l$인 두 부분 문자열을 비교해 봅시다. 이 길이의 부분 문자열 안에 들어가는 블록의 최대 길이를 찾습니다. 즉, $2^k \le l$을 만족하는 가장 큰 $k$를 찾습니다. 그러면 두 부분 문자열을 비교하는 것은 길이가 $2^k$인 서로 겹치는 두 블록을 비교하는 것으로 대체할 수 있습니다. 먼저 $i$와 $j$에서 시작하는 두 블록을 비교하고, 이들이 같다면 위치 $i + l - 1$과 $j + l - 1$에서 끝나는 두 블록을 비교해야 합니다:

$$\dots \overbrace{\underbrace{s_i \dots s_{i+l-2^k} \dots s_{i+2^k-1}}_{2^k} \dots s_{i+l-1}}^{\text{first}} \dots \overbrace{\underbrace{s_j \dots s_{j+l-2^k} \dots s_{j+2^k-1}}_{2^k} \dots s_{j+l-1}}^{\text{second}} \dots$$

$$\dots \overbrace{s_i \dots \underbrace{s_{i+l-2^k} \dots s_{i+2^k-1} \dots s_{i+l-1}}_{2^k}}^{\text{first}} \dots \overbrace{s_j \dots \underbrace{s_{j+l-2^k} \dots s_{j+2^k-1} \dots s_{j+l-1}}_{2^k}}^{\text{second}} \dots$$

다음은 비교의 구현입니다. 이 함수는 이미 계산된 $k$와 함께 호출된다고 가정한다는 점에 유의하십시오. $k$는 $\lfloor \log l \rfloor$로 계산할 수 있지만, 모든 $l$에 대해 $k$ 값을 미리 계산해 두는 것이 더 효율적입니다. 예를 들어 비슷한 아이디어를 사용하여 모든 $\log$ 값을 계산하는 희소 테이블에 관한 글을 참고하십시오.

int compare(int i, int j, int l, int k) {
    pair<int, int> a = {c[k][i], c[k][(i+l-(1 << k))%n]};
    pair<int, int> b = {c[k][j], c[k][(j+l-(1 << k))%n]};
    return a == b ? 0 : a < b ? -1 : 1;
}

추가 메모리를 사용하는 두 부분 문자열의 최장 공통 접두사¶

주어진 문자열 $s$에 대해 위치가 $i$와 $j$인 임의의 두 접미사의 최장 공통 접두사(LCP)를 계산하려고 합니다.

여기서 설명하는 방법은 $O(|s| \log |s|)$의 추가 메모리를 사용합니다. 선형 크기의 메모리만 사용하는 완전히 다른 접근법은 다음 절에서 설명합니다.

$O(|s| \log |s|)$ 시간에 접미사 배열을 구성하고, 각 반복에서 얻은 배열 $c[]$의 중간 결과를 기억해 둡니다.

$i$와 $j$에서 시작하는 두 접미사의 LCP를 계산해 봅시다. 길이가 2의 거듭제곱인 임의의 두 부분 문자열은 $O(1)$에 비교할 수 있습니다. 이를 위해 2의 거듭제곱 단위로(가장 큰 거듭제곱부터 가장 작은 거듭제곱 순으로) 문자열을 비교하고, 해당 길이의 부분 문자열이 같다면 그 길이를 답에 더한 뒤 같은 부분의 오른쪽에서 계속 LCP를 확인합니다. 즉, $i$와 $j$에 현재의 2의 거듭제곱을 더합니다.

int lcp(int i, int j) {
    int ans = 0;
    for (int k = log_n; k >= 0; k--) {
        if (c[k][i % n] == c[k][j % n]) {
            ans += 1 << k;
            i += 1 << k;
            j += 1 << k;
        }
    }
    return ans;
}

여기서 log_n은 밑이 $2$인 $n$의 로그를 내림한 값과 같은 상수를 나타냅니다.

추가 메모리 없이 구하는 두 부분 문자열의 최장 공통 접두사¶

이전 절과 같은 문제를 다룹니다. 문자열 $s$의 두 접미사에 대한 최장 공통 접두사(LCP)를 계산해야 합니다.

이전 방법과 달리 이 방법은 $O(|s|)$의 메모리만 사용합니다. 전처리의 결과는 하나의 배열입니다(이 배열 자체가 문자열에 관한 중요한 정보원이므로 다른 문제를 해결하는 데에도 사용됩니다). LCP 쿼리는 이 배열에서 RMQ 쿼리(구간 최솟값 쿼리)를 수행하여 답할 수 있으므로, 구현 방식에 따라 로그 시간, 나아가 상수 시간의 쿼리 시간도 달성할 수 있습니다.

이 알고리즘의 기반은 다음 아이디어입니다. 정렬된 순서에서 인접한 접미사의 각 쌍에 대해 최장 공통 접두사를 계산합니다. 다시 말해 배열 $\text{lcp}[0 \dots n-2]$를 구성하는데, 여기서 $\text{lcp}[i]$는 $p[i]$와 $p[i+1]$에서 시작하는 접미사들의 최장 공통 접두사의 길이와 같습니다. 이 배열은 문자열의 인접한 임의의 두 접미사에 대한 답을 제공합니다. 그러면 반드시 인접할 필요는 없는 임의의 두 접미사에 대한 답도 이 배열로부터 구할 수 있습니다. 실제로 접미사 $p[i]$와 $p[j]$의 LCP를 계산하라는 요청이 있다고 합시다. 그러면 이 쿼리의 답은 $\min(lcp[i],~ lcp[i+1],~ \dots,~ lcp[j-1])$이 됩니다.

따라서 이러한 배열 $\text{lcp}$가 있으면 문제는 RMQ로 환원되며, RMQ에는 복잡도가 서로 다른 다양한 풀이가 매우 많이 있습니다.

그러므로 주된 과제는 이 배열 $\text{lcp}$를 구축하는 것입니다. 이 배열을 $O(n)$ 시간에 계산할 수 있는 Kasai 알고리즘을 사용하겠습니다.

정렬된 순서(접미사 배열의 순서)에서 인접한 두 접미사를 살펴봅시다. 두 접미사의 시작 위치를 $i$와 $j$라 하고, 두 접미사의 $\text{lcp}$가 $k > 0$이라고 합시다. 두 접미사에서 첫 글자를 제거하면, 즉 접미사 $i+1$과 $j+1$을 취하면, 이 둘의 $\text{lcp}$가 $k - 1$이라는 것은 자명합니다. 그러나 이 값을 그대로 $\text{lcp}$ 배열에 기록할 수는 없는데, 이 두 접미사가 정렬된 순서에서 서로 인접하지 않을 수도 있기 때문입니다. 접미사 $i+1$은 물론 접미사 $j+1$보다 작지만, 둘 사이에 다른 접미사들이 있을 수 있습니다. 하지만 두 접미사 사이의 LCP는 그 사이 모든 전이 값의 최솟값이라는 것을 알고 있으므로, 그 구간 안의 임의의 두 쌍 사이의 LCP는 적어도 $k-1$이어야 하며, 특히 $i+1$과 그다음 접미사 사이의 LCP도 마찬가지라는 것을 알 수 있습니다. 그리고 그보다 더 클 수도 있습니다.

이제 알고리즘을 구현할 수 있습니다. 접미사들을 길이 순서대로 순회하겠습니다. 접미사 $i$에서 접미사 $i+1$로 넘어가는 것은 첫 글자를 제거하는 것과 정확히 같으므로, 이렇게 하면 직전 값 $k$를 재사용할 수 있습니다. 정렬된 접미사 목록에서 각 접미사의 위치를 알려 주는 추가 배열 $\text{rank}$가 필요합니다.

vector<int> lcp_construction(string const& s, vector<int> const& p) {
    int n = s.size();
    vector<int> rank(n, 0);
    for (int i = 0; i < n; i++)
        rank[p[i]] = i;

    int k = 0;
    vector<int> lcp(n-1, 0);
    for (int i = 0; i < n; i++) {
        if (rank[i] == n - 1) {
            k = 0;
            continue;
        }
        int j = p[rank[i] + 1];
        while (i + k < n && j + k < n && s[i+k] == s[j+k])
            k++;
        lcp[rank[i]] = k;
        if (k)
            k--;
    }
    return lcp;
}

$k$를 감소시키는 횟수는 최대 $O(n)$번이고(각 반복마다 최대 한 번이며, $\text{rank}[i] == n-1$인 경우에는 예외적으로 곧바로 $0$으로 재설정합니다), 두 문자열 사이의 LCP는 최대 $n-1$이므로, $k$를 증가시키는 횟수도 $O(n)$번뿐이라는 것을 쉽게 알 수 있습니다. 따라서 이 알고리즘은 $O(n)$ 시간에 동작합니다.

서로 다른 부분 문자열의 개수¶

접미사 배열과 LCP 배열을 계산하여 문자열 $s$를 전처리합니다. 이 정보를 이용하면 문자열에 포함된 서로 다른 부분 문자열의 개수를 계산할 수 있습니다.

이를 위해 위치 $p[0]$에서 시작하는 새로운 부분 문자열이 무엇인지, 그다음 $p[1]$에서 시작하는 것은 무엇인지 등을 차례로 생각해 보겠습니다. 실제로는 접미사들을 정렬된 순서로 취하면서 어떤 접두사가 새로운 부분 문자열이 되는지 살펴봅니다. 이렇게 하면 실수로 빠뜨리는 부분 문자열이 없습니다.

접미사들이 정렬되어 있으므로, 현재 접미사 $p[i]$는 접미사 $p[i-1]$과 일치하는 접두사를 제외한 모든 접두사에 대해 새로운 부분 문자열을 만들어 낸다는 것이 분명합니다. 즉, 처음 $\text{lcp}[i-1]$개를 제외한 모든 접두사입니다. 현재 접미사의 길이는 $n - p[i]$이므로, $p[i]$에서 시작하는 새로운 접두사는 $n - p[i] - \text{lcp}[i-1]$개입니다. 모든 접미사에 대해 합하면 최종 답을 얻습니다:

$$\sum_{i=0}^{n-1} (n - p[i]) - \sum_{i=0}^{n-2} \text{lcp}[i] = \frac{n^2 + n}{2} - \sum_{i=0}^{n-2} \text{lcp}[i]$$