10413 반복되는 부분 문자열

https://www.acmicpc.net/problem/10413

반복되는 부분 문자열

시간 제한	메모리 제한
5 초	256 MB

문제

문자열 분석은 DNA와 단백질 분자의 연구를 진행하기 위해 생물학과 화학 분야에서 종종 사용된다. 문자열 분석을 하는 데 있어, 긴 문자열에서 얼마나 많은 부분 문자열이 (적어도 두 번) 반복되는지 찾아내는 것이 중요한 문제이다.

이 문제에서 최대 100 000개의 알파벳 문자열이 주어지면, 여러분은 그 문자열 중 모든 반복되는 부분 문자열의 개수를 찾아야 한다. 이때, 두 번 이상 등장하는 모든 유일한 부분 문자열을 세어야 한다. 예를 들어, 주어지는 문자열이 aabaab이면 반복되는 부분 문자열은 총 5개가 있다: "a", "aa", "aab", "ab", "b". 또, 주어지는 문자열이 aaaaa이면 반복되는 부분 문자열은 총 4개가 있다: "a", "aa", "aaa", "aaaa". 반복되는 부분 문자열은 겹칠 수도 있다는 것에 유의하자 (두 번째 예시의 aaaa).

입력

첫 줄에는 테스트 케이스의 수 T가 정수로 주어진다. 입력은 최대 10개의 테스트 케이스로 이루어진다.

각 테스트 케이스마다 첫 번째 줄에 알파벳으로만 이루어진 문자열이 주어진다. 문자열의 길이는 최대 100 000이다.

출력

각 테스트 케이스마다, 주어지는 문자열에서 반복되는 모든 유일한 부분 문자열의 개수를 출력한다. 이때, 답은 부호있는 32비트 정수형으로 항상 표현할 수 있다.

예제 입력 1

3
aabaab
aaaaa
AaAaA

예제 출력 1

5
4
5

알고리즘 분류

• 문자열
• 접미사 배열과 lcp 배열 📌

 

🧬 반복되는 부분 문자열: 접미사 자동자(Suffix Automaton)로 풀어보는 문자열 분석

같은 부분 문자열이 얼마나 많이 반복되는지를 파악하는 것은 패턴 탐지에서 핵심입니다.
반복되는 모든 유일한 부분 문자열의 개수를 효율적으로 찾는 방법인 Suffix Automaton(SAM)을 알아봅시다.

📘 문제 요약

• 입력: 최대 길이 100,000의 문자열 (최대 10개 테스트 케이스)
• 출력: 두 번 이상 등장하는 모든 서로 다른 부분 문자열의 개수
• 주의: 부분 문자열은 겹쳐도 인정, 대소문자 구분

예시: 문자열 aabaab → 반복되는 부분 문자열: "a", "aa", "aab", "ab", "b" → 총 5개

💡 어떻게 풀까?

문제의 핵심은 다음과 같습니다:

1. 모든 부분 문자열을 탐색
2. 각 부분 문자열이 두 번 이상 등장하는 경우만 카운팅
3. 겹쳐도 인정

단순 브루트포스로 모든 부분 문자열을 세면 O(N²)의 시간복잡도로 시간 초과가 발생합니다.

from collections import defaultdict

def count_repeated_substrings(s):
    n = len(s)
    substr_count = defaultdict(int)

    # 모든 부분 문자열을 만들어서 등장 횟수 카운트
    for i in range(n):
        sub = ''
        for j in range(i, n):
            sub += s[j]
            substr_count[sub] += 1

    # 두 번 이상 등장하는 것만 카운트
    repeated_count = sum(1 for v in substr_count.values() if v >= 2)
    return repeated_count

# 입력 처리
T = int(input())
for _ in range(T):
    s = input().strip()
    print(count_repeated_substrings(s))

위 코드는 브루트포스 방식으로 모든 부분 문자열을 생성하여 카운팅합니다. 문자열 길이 N에 대해 부분 문자열 수가 O(N²)이므로, N이 100,000일 경우 절대로 처리할 수 없습니다.

✅ 해결책: 접미사 자동자(Suffix Automaton)

접미사 자동자(Suffix Automaton, SAM)는 문자열의 모든 부분 문자열을 선형 시간에 표현할 수 있는 자료구조입니다. 각 상태(state)는 특정 부분 문자열 집합을 대표하며, 링크(link) 구조를 통해 접미사 관계를 관리합니다.

🧠 알고리즘 설명

1. 접미사 자동자 구성

SAM을 구축하며, 각 상태에는 다음을 저장합니다:

• length[state]: 상태가 나타내는 문자열의 최대 길이
• link[state]: suffix link (길이가 짧은 접미사 상태로의 연결)
• nexts[state]: 문자별 전이(transition) 정보

2. 상태 정렬 및 등장 횟수 누적

SAM 구축 과정에서 각 상태(cur)가 한 번씩 생성될 때마다 cnt[cur] = 1로 초기화합니다. 이후, 길이별 counting-sort를 통해 상태를 오름차순으로 정렬한 뒤, order 배열을 역순으로 순회하며 등장 횟수를 부모 상태(link)로 누적합니다.

for v in reversed(order):
    p = link[v]
    if p != -1:
        cnt[p] += cnt[v]

이 부분은 상태를 길이 순서의 역순으로 순회하면서, 각 상태 v의 등장 횟수를 링크로 연결된 부모 상태 p에 전파하여, 짧은 접미사부터 긴 접미사로 정확한 등장 횟수를 계산하는 과정입니다.

3. 두 번 이상 등장하는 부분 문자열 세기

등장 횟수(cnt[v])가 2 이상인 상태만 고려하여, 해당 상태가 대표하는 새로운 부분 문자열의 개수를 더해줍니다.

if cnt[v] >= 2:
    ans += length[v] - length[link[v]]

각 상태 v가 추가로 대표하는 유일한 부분 문자열의 수는 length[v] - length[link[v]] 이고, cnt[v] ≥ 2인 경우에만 중복된 부분 문자열로 간주합니다.

💻 전체 코드

import sys, io
input = io.BufferedReader(io.FileIO(0), 1 << 17).readline

def solve():
    T = int(input())
    for _ in range(T):
        S = input().rstrip()
        n = len(S)

        max_states = 2 * n
        link = [-1] * max_states
        length = [0] * max_states
        cnt = [0] * max_states
        nexts = [dict() for _ in range(max_states)]

        sz = 1
        last = 0

        for ch in S:
            cur = sz
            sz += 1
            length[cur] = length[last] + 1
            cnt[cur] = 1

            p = last
            while p >= 0 and ch not in nexts[p]:
                nexts[p][ch] = cur
                p = link[p]

            if p == -1:
                link[cur] = 0
            else:
                q = nexts[p][ch]
                if length[p] + 1 == length[q]:
                    link[cur] = q
                else:
                    clone = sz
                    sz += 1
                    length[clone] = length[p] + 1
                    nexts[clone] = nexts[q].copy()
                    link[clone] = link[q]
                    cnt[clone] = 0

                    while p >= 0 and nexts[p].get(ch) == q:
                        nexts[p][ch] = clone
                        p = link[p]

                    link[q] = link[cur] = clone

            last = cur

        # counting-sort style
        max_len = max(length[:sz])
        bucket = [0] * (max_len + 1)
        for i in range(sz):
            bucket[length[i]] += 1
        for i in range(1, max_len + 1):
            bucket[i] += bucket[i-1]

        order = [0] * sz
        for i in range(sz-1, -1, -1):
            L = length[i]
            bucket[L] -= 1
            order[bucket[L]] = i

        for v in reversed(order):
            p = link[v]
            if p != -1:
                cnt[p] += cnt[v]

        ans = 0
        for v in range(1, sz):
            if cnt[v] >= 2:
                ans += length[v] - length[link[v]]

        print(ans)

if __name__ == "__main__":
    solve()

전체 코드는 다음과 같은 흐름으로 동작합니다:

1. 문자열 S의 각 문자에 대해 SAM을 확장하며 상태(cur) 및 필요 시 클론 상태(clone)를 생성합니다.
2. 모든 상태 생성 후, counting-sort로 상태를 길이별로 정렬하여 order 배열을 구성합니다.
3. order를 역순으로 순회하며, 각 상태의 등장 횟수(cnt)를 suffix 링크로 부모 상태에 누적합니다.
4. cnt[v] ≥ 2인 상태에 대해 length[v] - length[link[v]]를 더해 결과(ans)를 구합니다.

이 알고리즘의 시간 복잡도는 SAM 구축과 상태 정렬 및 누적 과정을 합쳐 O(N)이며, 메모리 복잡도는 최대 2N 상태를 사용하므로 O(N)입니다. 문자열 길이가 100,000일 때도 효율적으로 동작합니다.

요약: Suffix Automaton을 활용하면 문자열의 모든 부분 문자열을 선형 시간에 표현할 수 있으며, 중복된 부분 문자열의 개수를 효과적으로 계산할 수 있습니다.