파이썬으로 문자열 안에 포함된 부분 문자열 개수 구하기

문자열 s와 부분 문자열 t가 주어졌을 때, t가 s 안에 몇 번 등장하는지 세는 문제입니다.

예를 들어 s = "abaabcaabababaab", t = "aab"라고 하면 결과는 3이 됩니다. ab(aab)c(aab)abab(aab)처럼 "aab"가 세 위치에서 발견되기 때문입니다.

해결 접근 방법

슬라이싱과 반복문을 활용하면 간단하게 해결할 수 있습니다. 알고리즘은 다음과 같습니다.

• 카운터 변수 cnt를 0으로 초기화합니다.
• 인덱스 0부터 (len(s) - len(t))까지 반복합니다.
• 각 인덱스 i에서 s[i : i + len(t)]로 추출한 부분 문자열이 t와 같다면 cnt를 1 증가시킵니다.
• 반복이 끝나면 cnt를 반환합니다.

여기서 반복 범위를 len(s) - len(t) + 1로 설정하는 이유는, 마지막 가능한 시작 위치까지 모두 검사하기 위함입니다.

구현 예시

def solve(s, t):
   cnt = 0
   for i in range(0, len(s) - len(t) + 1):
      if s[i:i + len(t)] == t:
         cnt = cnt + 1
   return cnt

s = "abaabcaabababaab"
t = "aab"
print(solve(s, t))

입력

"abaabcaabababaab", "aab"

출력

3

대안: str.count() 메서드 활용

겹치지 않는(non-overlapping) 등장 횟수만 필요하다면 파이썬 내장 메서드 str.count()를 사용하는 것이 더 간단합니다.

s = "abaabcaabababaab"
t = "aab"
print(s.count(t))  # 출력: 3

단, 위의 직접 구현 방식은 시간 복잡도가 O(n × m)(n은 s의 길이, m은 t의 길이)이며, count() 역시 내부적으로 유사한 방식으로 동작하지만 코드가 훨씬 간결하다는 장점이 있습니다. 겹치는 패턴까지 세어야 하는 경우에는 직접 구현한 방식처럼 인덱스를 한 칸씩 이동하며 검사하는 로직이 유용합니다.