백준(1786) - 찾기 Python

백준(1786) - 찾기

문제풀이: KMP 알고리즘, 파이썬

KMP 알고리즘

KMP는 대표적인 문자열 매칭 알고리즘으로, 문자열과 패턴이 주어졌을 때, 문자열 안에서 주어진 패턴을 찾아내는 알고리즘 이다.

KMP 알고리즘을 사용하게 되면 O(N)의 시간 복잡도로 해결이 가능하다.

그 이유는 접두사, 접미사를 이용하여 불필요하게 반복되는 연산을 줄이기 때문이다.

KMP 알고리즘 정리

import sys
input = sys.stdin.readline

T = input().rstrip()
P = input().rstrip()

index_P = [0] * len(P)

j = 0
for i in range(1, len(P)):
    while j > 0 and P[i] != P[j]:
        j = index_P[j-1]
    if P[i] == P[j]:
        j += 1
        index_P[i] = j

j = 0
find = []
for i in range(len(T)):
    while j > 0 and T[i] != P[j]:
        j = index_P[j - 1]
    if T[i] == P[j]:
        if j == len(P) - 1:
            find.append(i - len(P) + 2)
            j = index_P[j]
        else:
            j += 1

print(len(find))
# print(*find) // 이 방법보다 join으로 출력하는 것이 시간 효율이 더 좋다.
print(' '.join(map(str, find)))

Reference

KMP 알고리즘

(https://hooongs.tistory.com/304?category=823477)