[Algorithm] C++ 백준 8235번 : Prefixuffix

아이디어 요약

접두사 P와 접미사 S가 서로 회전 동치이면서 길이가 최대가 되도록, 문자열 T를 T = A + B + X + B + A로 표현합니다. 그러면 P = A+B, S = B+A가 되어 회전 동치가 보장됩니다.
길이 제약 |P| = |S| ≤ n/2를 만족하려면 |A| = i, |B| = j에 대해 i + j ≤ n/2입니다.
중요한 단조성: i(=|A|)를 1 줄일 때 최적 j(=|B|)는 최대 2만 증가합니다. 따라서 i를 감소시키며 j를 두 포인터처럼 관리하면 인덱스 이동 총량이 O(n)입니다.
구간 비교는 롤링 해시로 O(1)에 수행합니다. 충돌 가능성을 낮추기 위해 모듈러 해시를 사용하고 인덱스 경계(빈 문자열 포함)를 안전하게 처리합니다.

C++ 풀이

 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
// 42jerrykim.github.io에서 더 많은 정보를 확인 할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

// 모듈러 롤링 해시 (P=917, MOD=993244853)
const ll P = 917;
const ll MOD = 993244853;

struct Hasher {
    vector<ll> ha, pw; // ha[i] = hash of s[i..], pw[k] = P^k mod MOD
    Hasher() {}
    explicit Hasher(const string& s) {
        int n = (int)s.size();
        ha.assign(n + 1, 0);
        pw.assign(n + 1, 1);
        pw[1] = P;
        for (int i = n - 1; i >= 0; --i) {
            ha[i] = (ha[i + 1] * P + s[i]) % MOD;
        }
        for (int i = 2; i <= n; ++i) pw[i] = pw[i - 1] * P % MOD;
    }
    // [l, r] (0-based, inclusive)
    inline ll get(int l, int r) const {
        if (r < l) return 0; // 빈 구간
        ll res = (ha[l] - ha[r + 1] * pw[r - l + 1]) % MOD;
        if (res < 0) res += MOD;
        return res;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    string t;
    if (!(cin >> n >> t)) return 0;

    // 1-indexed 보정용 센티넬을 앞에 두고 해싱
    string s = "#" + t;
    Hasher H(s);

    auto same = [&](int l1, int r1, int l2, int r2) -> bool {
        if (r1 < l1 && r2 < l2) return true;   // 둘 다 빈 문자열
        if (r1 < l1 || r2 < l2) return false;  // 한쪽만 빈 문자열
        return H.get(l1, r1) == H.get(l2, r2);
    };

    int ans = 0;
    int j = 0; // |B|
    for (int i = n / 2; i >= 1; --i) { // i = |A|
        j = min(n / 2 - i, j + 2);
        // 양 끝의 A가 같아야 T = A + B + X + B + A 성립
        if (!same(1, i, n - i + 1, n)) continue;

        ans = max(ans, i); // B = 0인 경우

        // B를 가능한 한 크게 확장
        while (j >= 0 && !same(i + 1, i + j, n - i + 1 - j, n - i)) --j;
        ans = max(ans, i + j); // |P| = |A| + |B|
    }

    cout << ans << '\n';
    return 0;
}