[Algorithm] cpp 백준 13576번: Prefix와 Suffix

문자열의 접두사이자 접미사인 모든 경계(보더)를 찾고, 각 길이가 부분 문자열로 등장하는 횟수를 구합니다. KMP 접두사함수(π)로 경계 사슬을 추출하고, π 누적 분포로 등장수를 계산하여 l 오름차순으로 출력합니다. O(n) 구현과 정당성·엣지케이스를 정리했습니다.

문제

링크: https://www.acmicpc.net/problem/13576
요약: 문자열 S에 대해 접두사이면서 접미사인 모든 길이 l을 찾아, 각 길이가 부분 문자열로 등장하는 횟수 c를 함께 출력한다. 결과는 l 오름차순.

제한/스펙

1 ≤ |S| ≤ 100,000
시간 제한 2초, 메모리 제한 512MB → 선형 시간 알고리즘 필요

입출력

예제 입력 1

1
ABACABA

예제 출력 1

예제 입력 2

1
AAA

예제 출력 2

접근 개요(아이디어 스케치)

핵심 관찰: 접두사와 접미사가 같은 길이 l은 접두사함수(π) 사슬을 따라 l = n, π[n-1], π[π[n-1]-1], ...로 얻을 수 있다.
등장 횟수: 각 위치 i에서 π[i] 값이 의미하는 길이의 접두사가 그 위치까지의 접미사와 일치하므로 cnt[π[i]]++. 이후 cnt를 경계 길이의 상위에서 하위로 누적해 작은 경계들의 등장횟수에 반영하고, 각 접두사 자체의 1회 등장을 더하면 전체 부분 문자열 등장수 c[l]을 얻는다.
알고리즘: (1) π 배열 계산, (2) cnt 누적, (3) 경계 길이 모아 정렬 후 (l, c[l]) 출력. 전체 O(n).

알고리즘 설계

접두사함수 π[i]: S[0..i]의 가장 긴 경계 길이. KMP 전처리로 선형 시간 계산.
등장수 카운팅:
- for i in [0..n-1]: cnt[π[i]]++
- for len from n down to 1: cnt[π[len-1]] += cnt[len]
- for l in [1..n]: cnt[l]++ (각 접두사 자체가 전체 문자열에서 1회 등장)
경계 수집: borders = [], k=n에서 시작해 k>0 동안 borders.push(k); k=π[k-1]. 정렬 후 길이 오름차순 출력.

복잡도

시간: O(n)
공간: O(n)

구현 (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
// 더 많은 정보는 42jerrykim.github.io 에서 확인하세요.
#include <bits/stdc++.h>
using namespace std;

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

    string s;
    if (!(cin >> s)) return 0;
    int n = (int)s.size();

    // 1) KMP prefix function (pi)
    vector<int> pi(n, 0);
    for (int i = 1; i < n; ++i) {
        int j = pi[i - 1];
        while (j > 0 && s[i] != s[j]) j = pi[j - 1];
        if (s[i] == s[j]) ++j;
        pi[i] = j;
    }

    // 2) Count occurrences of each prefix as a substring
    vector<long long> cnt(n + 1, 0);
    for (int i = 0; i < n; ++i) cnt[pi[i]]++;
    for (int len = n; len > 0; --len) cnt[pi[len - 1]] += cnt[len];
    for (int l = 1; l <= n; ++l) cnt[l]++; // count the prefix itself

    // 3) Collect all borders (prefix == suffix)
    vector<int> borders;
    for (int k = n; k > 0; k = pi[k - 1]) borders.push_back(k);
    sort(borders.begin(), borders.end());

    cout << borders.size() << '\n';
    for (int len : borders) cout << len << ' ' << cnt[len] << '\n';
    return 0;
}