백준 | 11478

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

알파벳 소문자로만 이루어진, 길이 1,000 이하의 문자열이 하나 주어진다.
이때 주어진 문자열의 서로 다른 부분 문자열의 개수를 구하는 문제이다.

중복되는 부분 문자열은 길이가 같은 부분 문자열에서만 나올 수 있는데,
이러한 케이스를 조건문으로 처리할 수도 있겠다는 생각을 했다.

근데 반복문으로 모든 부분 문자열을 다 구한 다음,
set() 변환을 통해 중복을 제거하고 갯수를 출력하는 게 더 깔끔한 풀이인 것 같아서..

그리고 시간 복잡도에 걸리지 않기 때문에 이렇게 짰다.

코드(정답)는 다음과 같다.

import sys


s = sys.stdin.readline().rstrip()

# i: 문자열 길이, j: 부분 문자열의 시작 인덱스
sub_str = []
for i in range(len(s)):
    for j in range(len(s) - i):
        sub_str.append(s[j:j + i + 1])

print(len(set(sub_str)))