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

문제 

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

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

---

아이디어

단순히 문자열을 슬라이싱하면 되는 문제이다.

0번 인덱스에서 시작해서 글자수를 늘려가면서 슬라이싱한 후 lst에 저장한다. 

 

문자열 s를 s = 'hello'라고 해보자. 

0번 인덱스에서 탐색한 부분 문자열은 h, he, hel, hell, hello 가 된다. 

1번 인덱스에서 탐색한 부분 문자열은 e, el, ell, ello 가 된다.

...

4번 인덱스에서 탐색한 부분 문자열은 o 하나밖에 존재하지 않는다.

 

즉, 우리가 고려해야 하는 값은 시작 인덱스 ( loc )와 해당 인덱스에서 시작하는 부분 문자열의 길이( k )이다. 

loc은 0부터 (문자열의 길이) - 1까지 움직일 수 있다. 

 

그리고 k는 1부터 시작해야 하며, loc과 k의 합의 최댓값은 (문자열의 길이)이다. 

즉, k + loc ≤ len_s → k ≤ len_s - loc 이 된다. 

 

이 경우에 대해서 for loop를 이용해서 순회하고 얻어진 부분 문자열을 리스트에 저장한다. 

그리고 set(list)를 수행해서 중복을 제거한 후 길이를 반환한다. 

---

Solution

s = input() 
lst = [] 

len_s = len(s)
for loc in range(0, len_s) :
    for k in range(1, len_s - loc + 1) : 
        val = s[loc:loc+k]
        lst.append(val)

print(len(set(lst)))