[Algorithm] C++ 백준 9120번: Oulipo 다국어

문제: BOJ 9120 - Oulipo 다국어

긴 텍스트 \(T\) 안에서 단어(패턴) \(W\)가 몇 번 등장하는지(겹침 허용) 세는 전형적인 문자열 매칭 문제다.
\(|T|\)가 최대 \(1{,}000{,}000\)까지 커질 수 있으므로, \(O(|W|\cdot|T|)\) 같은 단순 비교는 시간 초과가 나기 쉽고 KMP로 \(O(|W|+|T|)\)에 해결한다.

문제 정보

문제 링크: https://www.acmicpc.net/problem/9120

문제 요약:

• 테스트케이스마다 패턴 문자열 \(W\)와 텍스트 문자열 \(T\)가 주어진다.
• \(T\)에서 \(W\)가 등장하는 횟수를 출력한다.
• 등장 위치는 겹쳐도 된다. (예: \(W=\) “AA”, \(T=\) “AAAA” 이면 3번)

제한 조건:

• 시간 제한: 1초
• 메모리 제한: 128MB
• \(1 \le |W| \le 10{,}000\)
• \(|W| \le |T| \le 1{,}000{,}000\)
• 알파벳: ‘A’..‘Z’

입출력 예제

입력 1:

1
2
3
4
5
6
7

3
BAPC
BAPC
AZA
AZAZAZA
VERDI
AVERDXIVYERDIAN

출력 1:

1
2
3

1
3
0

접근 방식

핵심 관찰: KMP는 “현재까지 맞춘 접두사 길이”를 유지하며 한 번만 스캔한다

KMP는 패턴 \(W\)에 대해 접두사 함수(= 실패 함수) \(\pi\)를 만든다.

• \(\pi[i]\): \(W[0..i]\)의 접두사이면서 접미사인 것들 중 가장 긴 길이

텍스트 \(T\)를 왼쪽부터 훑으면서, 현재 일치한 길이 \(j\)를 유지한다.

• \(T[i]\)와 \(W[j]\)가 다르면, \(j=\pi[j-1]\)로 줄여서 “가능한 다음 후보”로 이동
• 끝까지 매칭(\(j = |W|-1\))되면 정답을 1 증가시키고, 겹침 허용을 위해 \(j=\pi[j]\)로 되돌린다

알고리즘 설계 (Mermaid Flowchart)

flowchart TD
    A["입력: 테스트케이스 수"] --> B["각 케이스마다 W, T 입력"]
    B --> C["pi = prefix_function(W)"]
    C --> D["i = 0, j = 0, cnt = 0"]
    D --> E{"i < |T| ?"}
    E -- "yes" --> F{"T[i] == W[j] ?"}
    F -- "no" --> G{"j > 0 ?"}
    G -- "yes" --> H["j = pi[j-1]"]
    G -- "no" --> I["i = i + 1"]
    H --> F
    F -- "yes" --> J{"j == |W|-1 ?"}
    J -- "no" --> K["i = i + 1
j = j + 1"]
    J -- "yes" --> L["cnt = cnt + 1
i = i + 1
j = pi[j]  (겹침 허용)"]
    K --> E
    L --> E
    E -- "no" --> M["cnt 출력"]

구현 포인트

• 겹침 처리: 매칭이 끝났을 때 \(j\)를 0으로 만들면 겹치는 매칭을 놓칠 수 있다. 반드시 j = pi[j] (또는 pi[m-1])로 이동한다.
• 입력 크기: \(T\)가 최대 \(10^6\)이므로 cin은 sync_with_stdio(false)와 tie(nullptr)를 켜고 사용한다.
• 정답 타입: 한 케이스에서 최대 \(10^6\)번까지 나올 수 있으므로 long long로 안전하게 출력한다.

복잡도 분석

코너 케이스 및 실수 포인트

구현 코드 (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

// 42jerrykim.github.io에서 더 많은 정보를 확인 할 수 있다
#include <bits/stdc++.h>
using namespace std;

static vector<int> build_pi(const string& p) {
    int m = (int)p.size();
    vector<int> pi(m, 0);
    for (int i = 1, j = 0; i < m; ++i) {
        while (j > 0 && p[i] != p[j]) j = pi[j - 1];
        if (p[i] == p[j]) pi[i] = ++j;
    }
    return pi;
}

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

    int tc;
    cin >> tc;
    while (tc--) {
        string w, t;
        cin >> w >> t;

        vector<int> pi = build_pi(w);
        long long cnt = 0;

        for (int i = 0, j = 0; i < (int)t.size(); ++i) {
            while (j > 0 && t[i] != w[j]) j = pi[j - 1];
            if (t[i] == w[j]) {
                if (j == (int)w.size() - 1) {
                    ++cnt;
                    j = pi[j]; // overlap allowed
                } else {
                    ++j;
                }
            }
        }

        cout << cnt << "\n";
    }
    return 0;
}

참고 문헌 및 출처

• 백준 9120번 문제