[파이썬] KMP 알고리즘
접두사와 접미사를 이용한 알고리즘이다
비교 과정을 보면
텍스트 : ABABABC
패턴 : ABABC 일 때,
1.
| 인덱스 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| 텍스트 | A | B | A | B | A | B | C |
| 패턴 | A | B | A | B | C |
2.
| 인덱스 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| 텍스트 | A | B | A | B | A | B | C |
| 패턴 | A | B | A | B | C |
index 4에서 불일치가 일어났을 때, index 0~1과 2~3의 패턴이 [AB]로 일치함을 이용해 중간 비교과정을 건너 뛰는 알고리즘이다.
이를 만들기 위해서는 전처리가 필요하다
비교하고 싶은 pattern이 abcdabcy라고 할 때
| 인덱스 | 문자열 | 최장 패턴 일치 길이(pi[j]) |
| 0 | a | 0 |
| 1 | ab | 0 |
| 2 | abc | 0 |
| 3 | abcd | 0 |
| 4 | abcda | 1 |
| 5 | abcdab | 2 |
| 6 | abcdabc | 3 |
| 7 | abcdabcy | 0 |
이런식으로 접두사(빨간색)과 접미사(파란색)의 패턴이 일치하는 가장 긴 길이를 pi라는 배열에 넣어주면 된다
pi 배열을 만들어 주는 이유는 문자열이 일치하지 않을 때 pi[j-1]의 위치로 비교를 계속 건너뛸 수 있기 때문이다
pi는 불일치시 점프할 패턴의 위치로 생각하면 편하다
예를 들어,
텍스트 : abcxabcdabxabcdabcy
패턴 : abcdabcy
아까 구한 pi배열의 값
| 인덱스 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| word[i] | a | b | c | d | a | b | c | y |
| pi[j] | 0 | 0 | 0 | 0 | 1 | 2 | 3 | 0 |
일 때,
| 텍스트 | a | b | c | x | a | b | c | d | a | b | x | a | b | c | d | a | b | c | y |
| 패턴 | a | b | c | d |
불일치가 일어났으니 우리는 pi배열을 이용해 점프할 수 있다.
불일치가 일어난 곳의 앞은 모두 일치했다는 의미이니 알고리즘으로 의미있게 사용할 수 있다.
바로 앞부분 [abc]를 보자.
pi[2(=패턴 c의 인덱스)]=0이므로 일치하는 패턴이 없다는 의미다.
word는 그대로 두고 pi[2]=0으로 패턴을 옮긴다
더 진행해보자.
| 텍스트 | a | b | c | x | a | b | c | d | a | b | x | a | b | c | d | a | b | c | y |
| 패턴 | a |
불일치가 일어났다. 패턴을 더이상 앞으로 점프 시킬 곳이 없으므로 비교를 시작할 word의 위치를 한 칸 미룬다
| 텍스트 | a | b | c | x | a | b | c | d | a | b | x | a | b | c | d | a | b | c | y |
| 패턴 | a | b | c | d | a | b | c |
c에서 불일치가 일어났다.
여기서 재밌는점은 우리는 패턴c(인덱스 2)와 x만 비교하면 된다는 것이다
그러니까 현재 불일치한 패턴 [c]바로 앞에 있는 일치한 파란색 패턴 [ab] 같은 파란색 패턴이 앞에 있으면 그쪽으로 점프하도록 하는 것이다
그렇게 되면,
| 텍스트 | a | b | c | x | a | b | c | d | a | b | x | a | b | c | d | a | b | c | y |
| 패턴 | a | b | c |
이렇게 바로 이동할 수 있다.
그럼 어차피 [ab], [ab] 패턴은 일치하기 떄문에 비교하지 않아도 되고 x와 c만 일치하는지 보면 된다
그리고, 이렇게 이동하는 값은 pi[5(=패턴 b의 인덱스)]=2 임을 통해 알 수 있다
현재 word의 인덱스는 고정해두고 pi[5]로 패턴의 인덱스를 이동시키는 것이다
이런식으로 계속 비교를 해서 word는 O(N)번 정도 돌고, pattern의 이동은 대략 O(M)정도 일어난다고 했을 때 KMP 알고리즘의 시간복잡도는 O(N+M)이라고 한다
알고리즘을 만들어보았다
T=input()
P=input()
def getPi(pattern):
pi = [0] * len(pattern)
j=0
for i in range(1, len(pi)): # i끝, j앞
while j > 0 and pattern[i] != pattern[j]:
j = pi[j - 1] #순간이동
if pattern[i] == pattern[j]:
j += 1
pi[i] = j
return pi
def kmp(word, pattern):
pi = getPi(pattern)
print(pi)
results = []
j=0
for i in range(len(word)): #i word, j pattern
while j > 0 and word[i] != pattern[j]:
j = pi[j - 1]
if word[i] == pattern[j]:
if j==len(pattern)-1:
results.append(i-len(pattern)+1)
j=pi[j]
else:
j+=1
return results
results = kmp(T, P)
print(len(results))
for r in results:
print(r+1)kmp 알고리즘으로 푸는 백준
https://www.acmicpc.net/problem/1786 문제의 답이다.
보면 알겠지만 어려우니까 많이 찾아보고 스스로 정리하기.
정리 안 해두면 볼 때마다 헷갈릴 것 같다!
참고