백준_1786_찾기

문제

1786번: 찾기

풀이

1) 실패 함수 PI

PI는 패턴에서 건너뛸 수 있는 문자의 개수를 의미하며 다음과 같이 구할 수 있다.

• ABAA의 PI = 1

	접두사	접미사	접두사==접미사
1(문자의 개수)	A	A	True
2(문자의 개수)	AB	AA	False
3(문자의 개수)	ABA	BAA	False

A, AB, ABA, ABAA에 대해 위와 같은 방법으로 PI값을 구하면, [0, 0, 1, 1]이라는 배열을 얻을 수 있다. (인덱스 0은 0으로 연산) 위처럼 하나씩 비교하는 방법을 사용하면 시간초과로 테스트를 통과하지 못한다. 여기에 KMP알고리즘을 이용하면 효율성 문제를 해결할 수 있다. 

• 문자열 ABAA의 PI배열

인덱스 i	0	1	2	3
문자열	A	B	A	A
PI_list	0	0
		≠
인덱스 j		0
문자열		A
PI_list		0

i를 1만큼 증가

인덱스 i	0	1	2	3
문자열	A	B	A	A
PI_list	0	0	1
			=	≠
인덱스 j			0	1
문자열			A	B
PI_list			0	0

JUMP j = PI_list[0] (=0)

인덱스 i	0	1	2	3
문자열	A	B	A	A
PI_list	0	0	1	1
				=
인덱스 j				0
문자열				A
PI_list				0

2) 문자열과 패턴 비교

연산 방법은 위와 동일하다.

• 패턴 ABAA, 문자열 ABACABAA의 비교

인덱스i	0	1	2	3	4	5	6	7
문자열	A	B	A	C	A	B	A	A
	=	=	=	≠
인덱스j	0	1	2	3
패턴	A	B	A	A
PI_list	0	0	1	1

JUMP j = PI_list[2] (=1)

인덱스i	0	1	2	3	4	5	6	7
문자열	A	B	A	C	A	B	A	A
				≠
인덱스j			0	1
패턴			A	B
PI_list			0	0

JUMP j = PI_list[0] (=0)

인덱스i	0	1	2	3	4	5	6	7
문자열	A	B	A	C	A	B	A	A
				≠
인덱스j				0
패턴				A
PI_list				0

i를 1만큼 증가

인덱스i	0	1	2	3	4	5	6	7
문자열	A	B	A	B	A	B	A	A
					=	=	=	=
인덱스j					0	1	2	3
패턴					A	B	A	A
PI_list					0	0	1	1

코드

from sys import stdin

s =  stdin.readline().rstrip("\n")
p = stdin.readline().rstrip("\n")

# 1. 실패함수 PI
pi_list = [0 for i in range(len(p))]
j = 0
for i in range(1, len(p)) :
    while (j>0 and p[i] != p[j]) :
        j = pi_list[j-1]
    if (p[i]==p[j]) :
        j = j+1
        pi_list[i] = j

# 2. 문자열과 패턴 비교
j = 0
ans = list()
for i in range(len(s)) :
    while (j>0 and s[i] != p[j]) :
        j = pi_list[j-1]
    if (s[i]==p[j]) :
        if j==len(p)-1 :
            ans.append(i-j+1)
            j = pi_list[j]
        else :
            j = j+1

print(len(ans))
for i in ans : print(i, end = " ")

알고리즘

• 문자열
• KMP

참고자료

https://www.youtube.com/watch?v=MKYSB2q4av0

https://www.youtube.com/watch?v=q-SMEUwcnJI

https://bowbowbow.tistory.com/6