백준(1786) - 찾기 Python
백준(1786) - 찾기
문제풀이: KMP 알고리즘, 파이썬
KMP 알고리즘
KMP는 대표적인 문자열 매칭 알고리즘으로, 문자열과 패턴이 주어졌을 때, 문자열 안에서 주어진 패턴을 찾아내는 알고리즘 이다.
KMP 알고리즘을 사용하게 되면 O(N)의 시간 복잡도로 해결이 가능하다.
그 이유는 접두사, 접미사를 이용하여 불필요하게 반복되는 연산을 줄이기 때문이다.
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
(https://hooongs.tistory.com/304?category=823477)
댓글남기기