파이썬으로 주어진 문자열에서 고유한 부분 문자열 개수 찾기

문자열 s가 하나 주어졌다고 가정해 봅시다. 우리가 해야 할 일은 이 문자열에서 만들어낼 수 있는 모든 고유한(중복되지 않는) 부분 문자열을 찾아 그 개수를 결과로 반환하는 것입니다.

예를 들어 입력이 s = 'prrstvt'라고 한다면, 출력은 26이 됩니다.

이때 얻을 수 있는 서로 다른 부분 문자열들은 다음과 같습니다.

'pr', 'rrs', 'st', 'rr', 'tv', 'rstv', 'stvt', 'prrstv', 'prrstvt', 'rrstvt', 's', 'prrst', 'stv', 'rrstv', 'rst', 'v', 'tvt', 'rstvt', 'r', 'rs', 'vt', 't', 'prr', 'p', 'rrst', 'prrs' — 총 26개입니다.

풀이 접근 방식

이 문제는 각 인덱스별로 집합(set)을 활용해 누적 관리하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

visited라는 새로운 딕셔너리(map)를 생성합니다.
문자열 s의 각 인덱스 ind와 해당 위치의 문자 let에 대해 반복합니다.
- temp라는 새로운 집합을 만듭니다.
- 만약 ind-1이 visited에 존재한다면, visited[ind-1]의 각 요소 has_let에 대해 has_let + let을 temp에 추가합니다. 즉, 직전 위치까지 끝나던 모든 부분 문자열 뒤에 현재 문자를 이어 붙여 새로운 부분 문자열을 만드는 것입니다.
- 현재 문자 let 하나만으로 이루어진 부분 문자열도 temp에 추가합니다.
- visited[ind] := temp로 저장합니다.
res라는 새로운 집합을 생성하고, visited에 담긴 모든 집합의 원소를 res에 병합(update)합니다. 집합 특성상 중복된 부분 문자열은 자동으로 제거됩니다.
마지막으로 res의 크기를 반환합니다. 이것이 곧 고유한 부분 문자열의 총개수입니다.

모든 부분 문자열은 어떤 위치를 끝점으로 가지므로, "각 위치에서 끝나는 부분 문자열"만 체계적으로 모으면 전체를 빠짐없이 커버할 수 있다는 점이 이 방법의 핵심입니다. 구현이 간단하고 직관적이라는 장점이 있으며, 입력 크기가 매우 클 경우에는 서픽스 트리(suffix tree)나 서픽스 오토마톤(suffix automaton) 같은 더 최적화된 기법을 고려할 수도 있습니다.

예제 코드

아래 구현을 통해 더 잘 이해해 보겠습니다.

def solve(s):
    visited = dict()
    for ind, let in enumerate(s):
        temp = set()
        if ind-1 in visited:
            for has_let in visited[ind-1]:
                temp.add(has_let+let)
        temp.add(let)
        visited[ind] = temp
    res = set()
    for sets in visited:
        res.update(visited[sets])
    return len(res)

print(solve('prrstvt'))

입력

'prrstvt'