Baekjoon 1786번 찾기

문제

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

걸린 시간

00 : 19 : 51

풀이

Python3

def getPi():
    pi = [0]*m
    j = 0
    for i in range(1, m):
        while j > 0 and P[j] != P[i]:
            j = pi[j-1]

        if P[j] == P[i]:
            j += 1
            pi[i] = j
    return pi

def kmp():
    ans = []
    pi = getPi()
    j = 0
    for i in range(0, n):
        while j > 0 and T[i] != P[j]:
            j = pi[j-1]

        if T[i] == P[j]:
            if j == m-1:
                ans.append(i-m+1)
                j = pi[j]
            else:
                j += 1
    return ans

if __name__ == "__main__":
    T = input() # 텍스트
    P = input() # 패턴

    n = len(T)
    m = len(P)

    result = kmp()
    print(len(result))
    for i in result:
        print(i+1)

다른 문제로 kmp 알고리즘을 공부한 다음 복습 개념으로 푼 문제이다.

kmp 알고리즘을 전혀 모르는 상태에서 문제에 주어진 설명만 읽고 이해한 후 구현하는 것이 과연 가능할까싶다.