[Python] BOJ 5525 - IOIOI

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

5525번: IOIOI

# N이 100만이하이고, M이 100만이하이므로 단순히 M에서 찾고자하는 문자열을 하나하나 비교해서 풀면

   O(N * M)이므로 시간초과가 난다. 해설들을 보니 M을 한번만 순회해서 찾는 O(M)방법도 많고 빠르긴 한데

   KMP알고리즘을 공부하기 위해 KMP를 사용해서 풀었다.

    (KMP 알고리즘은 O(N + M)에 동작한다.

 

# kmp 알고리즘에서 중요한 것은 prefix와 suffix이다. (접두사와 접미사)

   target의 접두사와 접미사가 같은 지점, 개수 등을 저장해놓으면 문자열에서 찾고자하는 target과

   문자열이 다를 때, 단순히 한칸을 건너서 또 비교하는 것이 아니라 중간에 일치하는 부분을 저장해놓음으써

   일치하는 부분만큼 뛰어넘어서 비교하는 것이 기본적인 알고리즘이다.

   https://bowbowbow.tistory.com/6 (이 블로그에 잘 정리되어있다.)

KMP : 문자열 검색 알고리즘

# make_table함수에서 table[i]는 문자열p의 0~i 까지의 부분 문자열 중에서 prefix == suffix가 될 수 있는

   부분 문자열 중에서 가장 긴 것의 길이이다.

 

# KMP함수에서 make_table(p)를 통해 table을 만들어주고 target문자열이 s안에 있는지 찾아준다.

   target을 p에서 찾았을때 찾았는지가 중요한게 아니라 총 p안에 target과 일치하는

   문자열이 몇개인지 모두 세줘야 하기 때문에 24번째 줄에서 target을 찾았을때

   cnt를 1증가시키고 j = table[j]를 해줌으로써 일치한 인덱스들을 건너뛰어준다.

 

def make_table(p):
    table = [0] * len(p)
    j = 0
    for i in range(1, len(p)):
        while j > 0 and p[i] != p[j]:
            j = table[j - 1]
 
        if p[i] == p[j]:
            j += 1
            table[i] = j
    return table

def KMP(p):
    table = make_table(p)
    cnt = 0
    j = 0
    for i in range(len(s)):
        while j > 0 and s[i] != p[j]:
            j = table[j - 1]
 
        if s[i] == p[j]:
            if j == len(p)-1:
                cnt += 1
                j = table[j]
            else:
                j += 1
    
    return cnt

N = int(input())
M = int(input())
s = input()
target = 'IO' * N + 'I'
ans = KMP(target)
print(ans)

(solved.ac 티어: 실버 2)