알고리즘

[BOJ] 1786 찾기 - kmp알고리즘

DDANDARA 2020. 10. 29. 14:39

www.acmicpc.net/problem/1786

 

1786번: 찾기

첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 공백으로 구분해 출력한다. 예컨대, T의 i～i+m-1번 문자와 P의 1～m

www.acmicpc.net

bowbowbow.tistory.com/6

kmp 알고리즘에 대해서는 위의 블로그에 설명이 아주 잘 되어있다.

 

KMP : 문자열 검색 알고리즘

문자열 검색이 뭐지? 워드프로세서를 사용할 때 찾기 기능을 사용한적 있을 겁니다. 브라우저에서도 Ctrl+F 단축키를 눌러 검색할 수 있습니다. 아래 이미지는 브라우저에서 "테이프"를 검색했

bowbowbow.tistory.com

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
import sys
 
def getpi(p):
    j = 0
    pi = [0] * len(p)
    for i in range(1, len(p)):
        while j > 0 and p[i] != p[j]:
            j = pi[j-1]
        if p[i] == p[j]:
            j += 1
            pi[i] = j
 
    return pi
 
def kmp(t, p):
    ans = []
    refac = getpi(P)
    j = 0
    for i in range(len(t)):
        while j > 0 and t[i] != p[j]:
            j = refac[j-1]
        if t[i] == p[j]:
 
            if j == len(p)-1:
                ans.append(i-len(p)+1)
                j = refac[j]
            else:
                j += 1
    return ans
 
T = sys.stdin.readline()
P = sys.stdin.readline()
T = T[0:-1]
P = P[0:-1]
answer = kmp(T, P)
 
print(len(answer))
for i in answer:
    print((i+1), end= ' ')
cs