[백준 문제풀이] 11478 - 서로 다른 부분 문자열의 개수

백준 문제풀이 11478번

풀이

예를 들어, ababc의 부분 문자열은 a, b, a, b, c, ab, ba, ab, bc, aba, bab, abc, abab, babc, ababc가 있고, 서로 다른것의 개수는 12개이다. ‘서로 다른 것’이므로 중복하지 않아야 하므로 set 자료형으로 중복을 제거하고, 위의 방법대로 센 수를 표로 나타내면 다음과 같다.

	j	j	j	j	j
i	a	ab	aba	abab	ababc
i		b	ba	bab	babc
i			a	ab	abc
i				b	bc
i					c

그리고 이 표를 문자열의 위치로 다시 나타내면 다음과 같다. ||j|j|j|j|j| |-|-|-|-|-|-| |i|0:1|0:2|0:3|0:4|0:5| |i||1:2|1:3|1:4|1:5| |i|||2:3|2:4|2:5| |i||||3:4|3:5| |i|||||4:5|

그리고 이걸 이중 for문으로 구현하면, j는 i부터 len(S)까지, 추가할 문자열은 S[i:j+i+1]과 같다. 이걸 코드로 구현하고 중복처리된 배열의 갯수를 세주면 정답처리가 된다.

코드

import sys

input = sys.stdin.readline

S = input().rstrip()

answer = []

j = 1
for i in range(len(S)):
    for j in range(i, len(S)):
        answer.append(S[i : j + 1])

print(len(set(answer)))