백준 - 5525

문제설명

특정 수 N이 주어졌을 때, IO * N + I의 열이 문자열에 몇 번 포함되어 있는지를 구하는 문제다.

서브태스크 문제로, N과 M의 길이가 매우 큰 경우가 제한사항으로 걸려있다.

접근방법

• 서브태스크 50점

1. 주어진 문자열 s에서 I를 만날 때마다 탐색 문자열 길이만큼을 확인
2. 탐색 문자열과 같은 경우 결과 값 1 증가
3. 다른 경우 continue 활용

• 서브태스크 100점

1. KMP 알고리즘을 이용하여, prefix suffix 개념을 활용
2. 테이블 생성 후, 주어진 문자열에 대해 수행

---

작성한 코드 1 (50점)

import sys

input = sys.stdin.readline

n = int(input())
m = int(input())

s = input().rstrip()

find = n * "IO" + "I"

result = 0

for i in range(0, len(s)-2):
    
    if s[i] == "I":
        if s[i:i+len(find)] == find:
            result += 1
    else:
        continue

print(result)

작성한 코드 2 (100점)

import sys

input = sys.stdin.readline

def makeTable(pattern):
    table = [0 for i in range(len(pattern))]
    j = 0
    for i in range(1, len(pattern)):
        while(j>0 and pattern[i] != pattern[j]):
            j = table[j-1]

        if pattern[i] == pattern[j]:
            table[i] = j+1
            j += 1
    return table

def KMP(parent, pattern):
    table = makeTable(pattern)

    j = 0
    result = 0

    for i in range(len(parent)):                    # 전체 길이를 돌며
        while(j>0 and parent[i] != pattern[j]):     # 하나씩 비교
            j = table[j-1]                          # 
        
        if parent[i] == pattern[j]:                 # 글자가 일치하는 경우
            if j == len(pattern) - 1:               # 마지막 인덱스
                result += 1                         # 결과 +1
                j = table[j]                        
            else:
                j+= 1                               # 마지막 인덱스가 아닌 경우
    return result 

n = int(input())
m = int(input())
parent = input().rstrip()

pattern = n * "IO" + "I"

result = KMP(parent, pattern)
print(result)