[Python 3] 백준 1786-찾기

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

1786번: 찾기

KMP를 그대로 이용하는 문제.

KMP 알고리즘

Knuth-Morris-Pratt 알고리즘의 줄임말이다. 입력으로 전체 문자열과 찾고 싶은 문자열을 받는다.

뇌를 비우고 문자열을 확인한다면, 첫 번째 문자부터 끝까지 다 뒤져 보면서 맞는 것을 찾을 수 있겠지만, 전체 문자열의 길이=N, 찾고 싶은 문자열의 길이=M이라 하면 O(NM)이다. 못 써먹는다.

다만, 여기서 기존의 결과를 이용하여 처음부터 가망이 없는 결과를 다 스킵한다면 시간복잡도를 줄일 수 있다.

예를 들어서, 문자열 'ABC ABCDAB ABCDABCDABDE'에서 'ABCDABD'를 찾는다고 한다면...

• 최초에는, 첫 세 글자 ABC만 일치한다. 
• 그 이후 2번째부터~4번째부터 시작할 때는 첫판부터 OUT.
• 5번째부터 7번째까지는 ABC가 전부 일치한다. 즉 정석적으로 보면 1번째 글자 체크 이후 5번째로 바로 스킵해야 함.

이를 빠르게 찾기 위해서는, 첫 문자열의 끝 부분과 이후에 확인해야만 하는 문자열이 중첩되므로, Prefix(접두사)와 Suffix(접미사)가 같은 경우를 찾아야 한다. 예를 들어서 abcdabc 같은 경우 앞의 세 글자인 abc와 뒤의 세 글자인 abc가 접두사=접미사 관계를 보여준다. 이러한 접두사-접미사 관계는 첫 글자부터 특정 글자까지 전부 찾아내야 한다.

ABCDABD에 대해 다 찾아보면...

i	부분문자열	접두사/접미사	pi[i]
0	A	A	1
1	AB	-	0
2	ABC	-	0
3	ABCD	-	0
4	ABCDA	A	1
5	ABCDAB	AB	2
6	ABCDABD	-	0

pi는 인덱스 i인 문자열의 최대 접두사/접미사 길이이다.

이 경우 pi는 [1, 0, 0, 0, 1, 2, 0]이다. 

문제의 경우, 최초 3글자만 일치하므로 pi[2]를 체크.

0	1	2	3	4	5	6	7	8	9
A	B	C		A	B	C	D	A	B
A	B	C	D

0	1	2	3	4	5	6	7	8	9
A	B	C		A	B	C	D	A	B
			A

4	5	6	7	8	9	10	11	12	13
A	B	C	D	A	B		A	B	C
A	B	C	D	A	B	D

P[5]=2. 즉 8번째부터 시작한다.

8	9	10	11	12	13	14	15	16	17
A	B		A	B	C	D	A	B	C
A	B	C

8	9	10	11	12	13	14	15	16	17
A	B		A	B	C	D	A	B	C
	A	B

8	9	10	11	12	13	14	15	16	17
A	B		A	B	C	D	A	B	C
		A

11	12	13	14	15	16	17	18	19	20
A	B	C	D	A	B	C	D	A	B
A	B	C	D	A	B	D

15	16	17	18	19	20	21	-	-	-
A	B	C	D	A	B	D	-	-	-
A	B	C	D	A	B	D	-	-	-

i=15, 즉 앞에서부터 16번째 글자부터 찾고 싶은 문자열이 나온다. 끝!

알고리즘의 구현

탐색을 시작하는 위치를 begin, 현재 일치하는 글자 수를 matched라 하자.

그러면 begin이 글자 총 개수를 넘지 않는 동안만, 이하의 행동을 반복한다.

• matched<m이고 begin+matched 위치에 있는 글자가 찾고자 하는 문자열의 matched번째 글자와 동일하면 matched를 1 증가시키고 matched가 m에 도달하면 찾는 데 성공했으므로 결과값을 추가한다.
• 그 외의 경우, 첫판부터 맞지 않는 경우(matched=0) begin을 1칸 뒤로 민다. 그렇지 않다면, begin을 matched-pi[matched-1]로 바꾸고 matched를 pi[matched-1]로 바꾼다. 즉, 접미사 쪽부터 조사를 시작한다.

pi 배열 찾기

pi 배열을 빠르게 구하는 방법 역시 KMP 알고리즘과 동일하다. 

단, 이 경우에는 begin<=n-m이 아닌, begin+matched가 m보다 작을 경우만 가능. 이 때는 접두사-접미사 관계를 만족시킬 때에만 matched를 증가시킨다.

def getpartialmatch(N):
  m=len(N)
  pi=[0 for i in range(m)]
  begin=1
  matched=0
  while begin+matched<m:
    if N[begin+matched]==N[matched]:
      matched+=1
      pi[begin+matched-1]=matched
    else:
      if matched==0:
        begin+=1
      else:
        begin+=matched-pi[matched-1]
        matched=pi[matched-1]
  return pi

def KMP(H, N):
  n=len(H)
  m=len(N)
  ret=[]
  pi=getpartialmatch(N)
  begin=0
  matched=0
  while begin<=n-m:
    if matched<m and H[begin+matched]==N[matched]:
      matched+=1
      if matched==m:
        ret.append(begin)
    else:
      if matched==0:
        begin+=1
      else:
        begin+=matched-pi[matched-1]
        matched=pi[matched-1]
  return ret

T=str(input())
P=str(input())
x=KMP(T, P)
print(len(x))
for i in x:
  print(i+1, end=" ")