파이썬으로 문자열 s의 고유한 부분 문자열 개수 세기

문제 소개

문자열 s가 주어졌을 때, s에서 만들 수 있는 중복되지 않는 비어 있지 않은 부분 문자열(distinct non-empty substrings)의 개수를 구하는 것이 목표입니다.

예를 들어 입력이 s = "abaa"라면, 가능한 부분 문자열은 ["a", "b", "ab", "ba", "aa", "aba", "baa", "abaa"]로 총 8가지이므로 결과값은 8이 됩니다.

접근 방법: 트라이(Trie) 활용

이 문제는 트라이(Trie) 자료구조를 이용하면 효율적으로 해결할 수 있습니다. 문자열의 모든 시작 위치에서 끝까지 탐색하며 각 부분 문자열을 트라이에 삽입하면, 동일한 경로는 자동으로 하나로 병합됩니다. 따라서 트라이에 존재하는 노드의 개수가 곧 고유한 부분 문자열의 개수와 같습니다.

풀이 과정은 다음과 같습니다.

trie를 빈 딕셔너리(맵)로 초기화합니다.
n을 문자열 s의 길이로 설정합니다.
i를 0부터 n-1까지 반복합니다.
- curr을 trie로 설정합니다.
- j를 i부터 n-1까지 반복합니다.
  - c = s[j]
  - c가 curr에 없다면 curr[c]에 새 딕셔너리를 생성합니다.
  - curr을 curr[c]로 이동시킵니다.
  - curr["*"] = True로 설정하여 문자열의 끝을 표시합니다.
큐(deque)를 생성하고 trie를 삽입한 뒤, BFS 방식으로 모든 노드를 순회하며 개수를 셉니다.
ans를 0으로 초기화하고, 큐가 빌 때까지 다음을 반복합니다.
- ans를 1 증가시킵니다.
- 큐에서 왼쪽 항목을 꺼내 t에 저장합니다.
- t의 각 키 c에 대해, "*"가 아니라면 t[c]를 큐 끝에 추가합니다.
루트 노드를 제외한 실제 노드 수인 ans - 1을 반환합니다.

예제 코드

아래 구현을 통해 더 자세히 이해해 보겠습니다.

from collections import deque

def solve(s):
    trie = {}
    n = len(s)
    for i in range(n):
        curr = trie
        for j in range(i, n):
            c = s[j]
            if c not in curr:
                curr[c] = {}
            curr = curr[c]
            curr["*"] = True

    q = deque([trie])
    ans = 0
    while q:
        ans += 1
        t = q.popleft()
        for c in t:
            if c != "*":
                q.append(t[c])
    return ans - 1

s = "abaa"
print(solve(s))

입력

"abaa"

출력

시간 복잡도 정리

모든 시작 위치 i에 대해 끝 위치 j까지 탐색해야 하므로, 이 알고리즘의 시간 복잡도는 O(n²)입니다. 공간 복잡도 역시 트라이에 저장되는 노드 수에 따라 O(n²)까지 커질 수 있습니다. 입력 크기가 매우 클 경우에는 접미사 배열(Suffix Array)이나 접미사 트리(Suffix Tree)를 활용하면 O(n log n) 또는 O(n) 시간에 해결할 수 있다는 점도 참고하면 좋습니다.