11478번: 서로 다른 부분 문자열의 개수 (acmicpc.net)

##
서로 다른 부분 문자열의 개수를 세기

##
S = input()
l = []

for i in range(1,len(S)+1):
    for j in range(len(S)):
        if j+i > len(S): break
        l.append(S[j:j+i])

print(len(set(l)))
문제 자체는 그냥 풀었는데




```python
s = input()
ans=0
for i in range(1, len(s)+1):
    subset = set()
    for j in range(len(s)-i+1):
        subset.add(s[j:j+i])
    ans+=len(subset)
print(ans)
```

해시 충돌이 발생할경우 최악의 경우 시간 복잡도가 O(n)
길이별로 따로 체크한다면 해시충돌을 줄일 수 있다.
어떻게 코드 짜느냐에 따라 시간차이가 2~3배정도 난다

내가 제출한 코드의 경우 break문 체크하는 시간까지 더해져서 더 느린 결과가 나왔다.