[백준 11478번] 서로 다른 부분 문자열의 개수 (Python 파이썬) 풀이 방법

백준 11478번 <서로 다른 부분 문자열의 개수> 문제 보기

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

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

 

 

백준 11478번 <서로 다른 부분 문자열의 개수> 문제 풀이

S = input().strip()

result = set()

for i in range(len(S)):
  for j in range(len(S)-i):
    result.add(S[j:j+i+1])
    
print(len(result))

 

 

 

• 전체문자열 S의 길이는 5라고 가정
• i는 0부터 4까지 (확인하는 부분문자열의 길이-1)
• j는 0부터 len(S)-i까지 (부분문자열의 길이가 전체문자열의 길이를 넘지 않도록 (전체문자열 길이(len(S))에서 부분문자열 길이(i)를 제거)
• 중복을 제거해주는 set을 사용해서 문자열을 더하고, 이후에 그 set 길이를 출력

 

 

 

다른 풀이

S = input()
stringSet = set()
stringLength = len(S)
answer = 0

for i in range(stringLength):
  for j in range(1,stringLength+1):
    if i+j > stringLength:
      break
    stringSet.add(S[i:i+j])

print(len(stringSet))

 

• i+j가 stringLength를 넘어갈 경우 break문 사용
• 0번째 자리에서 시작되는 모든 문자열, 1번째 자리에서 시작되는 모든 문자열 ,,, 순으로 탐색

 

 

s = input()

result = set()
for i in range(0,len(s)):
    for j in range(i+1,len(s)+1):
        result.add(s[i:j])

print(len(result))

 

• 윗 분과 비슷한 방법