문제
풀이
이중 for문을 통해서 하나하나씩 비교해가는 것은 O(NM) 시간복잡도를 가져 매우 비효율적이다.
위 문제는 O(N+M) 시간복잡도를 가지는 전형적인 KMP 알고리즘 문제이다. 탐색으로 얻은 정보를 최대한으로 활용하여 빠르게 일치하는 것을 확인하는 알고리즘이다.
먼저 접두사(prefix)와 접미사(suffix)에 대한 이해가 필요하다. 접두사와 접미사란 apple에서 a, ap, app, appl, apple가 접두사가 되며, 접미사란 e, le, ple, pple, apple가 된다.
접두사와 접미사가 일치하는 최대의 길이를 담아 놓은 함수를, 실패함수 pi라고 정의한다.
i를 텍스트(s)의 index 처음부분, j를 찾고자 하는 문자열(m)의 index라고 정의한다면, pi배열을 통해서 만약 s[i] != m[j]가 나타날 때까지 j를 1씩 증가시킨다.
s[i]와 m[j]가 일치하지 않는다면, j의 index를 직전 문자열의 pi배열 값으로 변경시킨다. 이는 직전 문자열의 pi배열값까지는 이미 일치하다는 것을 알고 있기 때문이다.
그 이후 j가 0이 되어 while문을 빠져나왔을 때, s[i]와 m[j]가 일치했을 때, j를 1씩 증가시키며 끝에 도달했을 땐 정답 list에 index를 넣는다.
이를 KMP 알고리즘이라고 한다.
pi배열을 구하는 것 또한 이런 알고리즘을 이용한다. m 문자열을 서로 비교시키는데, 일치한다면, j를 증가시키고, pi[i]에 j값을 넣어둔다.
일치하지 않는다면, 지금껏 구한 pi배열을 통해 일치된 정보 다음에서 탐색을 계속 이어나간다. 이를 통해 pi의 배열을 완성시킨다.
Reference에서 너무나 자세히 설명해주셨다.
소스 코드
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
40
41
42
import sys
from math import *
def getpi():
pi = [0] * len(m)
j = 0
for i in range(1, len(m)):
while(j>0 and m[i] != m[j]):
j = pi[j-1]
if(m[i] == m[j]):
j = j+1
pi[i] = j
return pi
def kmp(pi):
j = 0
result = []
for i in range(0, len(s)):
while(j>0 and s[i] != m[j]):
j = pi[j-1]
if(s[i] == m[j]):
if(j == len(m)-1):
result.append(i- len(m) + 2)
j = pi[j]
else:
j = j+1
print(len(result))
for i in result:
print(i, end = ' ')
s = input()
m = input()
kmp(getpi())
