[Algorithm] C++ 백준 1605번: 반복 부분문자열

BOJ 1605 반복 부분문자열 문제다. Suffix Array와 LCP Array를 활용해 가장 긴 반복 부분문자열의 길이를 O(n log n) 시간복잡도로 구한다. 배가법(doubling)과 카운팅 소트로 접미사 배열을 구성하고, Kasai 알고리즘으로 LCP 배열을 계산한다. 인접한 접미사들의 최대 LCP가 정답이다.

문자열 안에서 적어도 한 번 이상 반복되는 부분문자열(즉, 전체 문자열에서 두 번 이상 등장하는 부분문자열)의 최대 길이를 구하는 문제이다. 길이 \(L\) 은 최대 200,000이므로, 단순한 모든 구간 비교는 시간 내에 불가능하다.

문제: BOJ 1605 — 반복 부분문자열

문제 정보

시간 제한: 2초
메모리 제한: 128MB
입력 제한: L ≤ 200,000, 문자열은 소문자

접근 방식

가장 긴 반복 부분문자열의 길이는 접미사 배열(Suffix Array)과 LCP 배열(Kasai)로 구할 수 있다.
문자열의 모든 접미사를 사전순으로 정렬한 뒤, 인접한 접미사들 간 LCP(최장 공통 접두사)의 최댓값이 정답이 된다.
시간 복잡도: 접미사 배열 배가법(O(n log n)) + Kasai O(n) ⇒ O(n log n)

참고로, 이 문제는 해시(이중 롤링 해시) + 이분 탐색(O(n log n))으로도 풀 수 있으나, 본 글에서는 접미사 배열 기반 풀이를 제공한다.

C++ 풀이 (Suffix Array + LCP)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <bits/stdc++.h>
using namespace std;

// Stable counting sort by key in range [0, K)
static void counting_sort(vector<int>& sa, const vector<int>& key, int K) {
    int n = (int)sa.size();
    vector<int> cnt(K + 1, 0), tmp(n);
    for (int i = 0; i < n; ++i) cnt[key[i]]++;
    for (int i = 1; i <= K; ++i) cnt[i] += cnt[i - 1];
    for (int i = n - 1; i >= 0; --i) tmp[--cnt[key[sa[i]]]] = sa[i];
    sa.swap(tmp);
}

static vector<int> build_sa(const string& s) {
    int n = (int)s.size();
    vector<int> sa(n), rnk(n), tmp(n);
    for (int i = 0; i < n; ++i) {
        sa[i] = i;
        rnk[i] = (unsigned char)s[i];
    }
    for (int k = 1;; k <<= 1) {
        int maxRank = *max_element(rnk.begin(), rnk.end());
        int K = max(maxRank + 2, 258);
        vector<int> key2(n);
        for (int i = 0; i < n; ++i) key2[i] = (i + k < n ? rnk[i + k] + 1 : 0);

        counting_sort(sa, key2, K);
        vector<int> key1(n);
        for (int i = 0; i < n; ++i) key1[i] = rnk[i] + 1;
        counting_sort(sa, key1, K);

        tmp[sa[0]] = 0;
        for (int i = 1; i < n; ++i) {
            int a = sa[i - 1], b = sa[i];
            bool diff = (rnk[a] != rnk[b]) || (key2[a] != key2[b]);
            tmp[b] = tmp[a] + (diff ? 1 : 0);
        }
        rnk.swap(tmp);
        if (rnk[sa[n - 1]] == n - 1) break;
    }
    return sa;
}

static vector<int> build_lcp(const string& s, const vector<int>& sa) {
    int n = (int)s.size();
    vector<int> rank(n), lcp(max(0, n - 1));
    for (int i = 0; i < n; ++i) rank[sa[i]] = i;
    int h = 0;
    for (int i = 0; i < n; ++i) {
        int r = rank[i];
        if (r == n - 1) { h = 0; continue; }
        int j = sa[r + 1];
        while (i + h < n && j + h < n && s[i + h] == s[j + h]) ++h;
        lcp[r] = h;
        if (h > 0) --h;
    }
    return lcp;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int L; string s;
    if (!(cin >> L)) return 0;
    cin >> s;
    if (s.empty()) { cout << 0 << '\n'; return 0; }
    auto sa = build_sa(s);
    auto lcp = build_lcp(s, sa);
    int ans = 0;
    for (int v : lcp) ans = max(ans, v);
    cout << ans << '\n';
    return 0;
}