[BOJ 1605] 반복 부분문자열

백준 문제 링크

🔍 문제 분석

자세한 내용은 접미사 배열(Suffix Array) 및 LCP(Longest Common Prefix)접미사 배열 페이지를 참고한다.

• 반복되는 부분 문자열은 접미사들의 공통 접두사로 이해할 수 있다. 따라서, LCP 배열을 계산한 뒤 배열의 최댓값을 통해서 반복되는 부분 문자열의 최댓값을 계산할 수 있다.

💻 코드 구현

#include <bits/stdc++.h>
#define fastio cin.tie(0)->ios::sync_with_stdio(0)

using namespace std;
using ll = long long;
using pi = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vvll = vector<vector<ll>>;
using vll = vector<ll>;
using vpi = vector<pi>;

constexpr int MAX = 200'000;

int n, sa[MAX], g[MAX], lcp[MAX];
string s;

int main() {
    fastio;

    cin >> n >> s;

    for (int i = 0; i < s.size(); ++i) {
        sa[i] = i;
        g[i] = s[i];
    }

    for (int i = 0; (1 << i) < s.size(); i++) {
        auto cmp = [&] (int lhs, int rhs) {
            if (g[lhs] == g[rhs]) {
                lhs += 1 << i;
                rhs += 1 << i;
                if (lhs < s.size() && rhs < s.size()) {
                    return g[lhs] < g[rhs];
                } 
                return lhs > rhs;
            }
            return g[lhs] < g[rhs];
        };

        sort(begin(sa), begin(sa) + s.size(), cmp);

        int tmp[MAX] = { 0 };
        for (int j = 0; j < s.size() - 1; ++j) {
            tmp[j + 1] = tmp[j] + cmp(sa[j], sa[j + 1]);
        }

        for (int j = 0; j < s.size(); ++j) {
            g[sa[j]] = tmp[j];
        }

        if (g[s.size() - 1] == s.size() - 1) break;
    }

    int k = 0;
    for (int i = 0; i < s.size(); ++i) {
        if (g[i] == 0) continue;
        while (
            (i + k < s.size() && sa[g[i] - 1 < s.size()]) &&
            s[i + k] == s[sa[g[i] - 1] + k]
        ) ++k;
        lcp[g[i]] = k--;
        k = max(k, 0);
    }

    cout << *max_element(begin(lcp), begin(lcp) + s.size());
}

📝 코드 설명

🔧 트러블 슈팅

📚 참고자료

• 접미사 배열(Suffix Array) 및 LCP(Longest Common Prefix)접미사 배열