[백준 11478번] 파이썬 - 서로 다른 부분 문자열의 개수

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

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

 

 

 

# 조건

• 문자열 S가 주어졌을 때, S의 서로 다른 부분 문자열의 개수를 구하여라
• 부분 문자열은 S에서 연속된 일부분을 말하며, 1보다 크거나 같아야 된다.
• 예를 들어, ababc의 부분 문자열은 a, b, a, b, c, ab, ba, ab, bc, aba, bab, abc, abab, babc, ababc가 있고, 서로 다른것의 개수는 12개이다.

 

# 접근 방법

• S를 1에서 길이수만큼 부분 집합을 구해준다.
• 이 때, 서로 다른 것들을 구해야되므로 SET에 담아준 후 SET의 크기를 출력해준다.

 

s = input().rstrip()  
arr = set()  
for i in range(len(s)+1):  
    for j in range(i,len(s)+1):  
        arr.add(s[i:j])  
print(len(arr)-1) # 빈 문자열이 포함되어 -1을 해주었다