[자료구조/집합] 백준 11478 서로 다른 부분 문자열의 개수 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

11478번: 서로 다른 부분 문자열의 개수

 

 

2. 문제 풀이

 주어진 문자열 S의 부분 문자열 개수를 구하는 문제입니다.

 부분 문자열은 S의 연속된 일부분을 뜻합니다. 

 

 

반응형

 

3. 코드

# 입력
S = input().rstrip()

# 집합으로 구현
char_set = set()

len_S = len(S)
for i in range(0, len_S):
    for j in range(i, len_S):
        char_set.add(S[i:j+1])

print(len(char_set))

 여기서 주의해야할 점은 '중복 제외'입니다.

 주어진 문자열이 aaa라고 할 때, 부분 문자열은 a, aa, aaa입니다.

 a, a, a, aa, aa, aaa 와 같이 같은 부분 문자열을 중복해서 산정하지 않도록 집합 자료구조를 사용합니다.