KMP 알고리즘

KMP 알고리즘

KMP 알고리즘 (Knuth-Morris-Pratt)

시간복잡도 O(n) 으로 문자열에서 다른 문자열이을몇번 찾을 수 있는지 확인하는 알고리즘

예를 들어 문자열 ‘ababacabacaabacaaba’ 에서 ‘abacaaba’(패턴)가 있는지, 있다면 몇번 찾을 수 있는지 확인하고 싶다고 하자.

그렇다면 아래와 같이 문자열의 길이만틈 패턴의 길이를 계속 순차적으로 확인해 나가야 할 것이다.

이와 같은 방법으로 모두 확인하게 되면 시간복잡도는 O(n*m) (n:문자열의 길이, m: 패턴의 길이)가 될 것이다.

KMP 알고리즘의 핵심은 위 처럼 모든 경우를 다 비교하지 않는 것에 있다.

비교하면서 반복되는 구간은 점프해서 넘어갈 수 있는 것이다.

이렇게 하기 위해서 접두사와 접미사가 얼마나 같은지 확인하는 테이블을 따로 만들어 줘야 한다.

• 접두사 접미사 확인 테이블

1. 먼저 테이블을 0 으로 초기화 시킨다.

2. i와 j를 통해서 테이블을 채워 나간다.

1. i 는 1부터 시작하고, j 는 0으로 시작한다. 2. pattern[i] 와 pattern[j] 가 같다면 j를 1증가시키고 그 증가 시킨 j값을 table[i]에 넣는다. 3. pattern[i] 와 pattern[j] 가 다르고 j가 0이라면 i 를 1 증가시키고 다시 반복한다. 4. pattern[i] 와 pattern[j] 가 다르고 j가 0 이 아니라면, j를 1 감소시킨다.

1. 위의 방법으로 테이블을 완성한 모습이다.

   테이블에 해당하는 숫자의 인덱스까지는 접미사와 접두사가 일치한다는 것을 의미한다.

• 테이블을 만드는 것을 python 코드로 확인해 보자.

table = [0] * len(pattern)

j = 0
for i in range(1, len(pattern)):
    while j > 0 and pattern[i] != pattern[j]:
        j = table[j-1]
    if pattern[i] == pattern[j]:
        j += 1
        table[i] = j

이제 테이블을 작성했으니, 어떤방법으로 반복되는 연산은 점프하면서 문자열과 패턴을 비교하는지 확인해보자.

개념은 테이블을 만드는 방법과 유사하다.

1. 위와 같이 i는 문자열의 인덱스만큼 하나씩 증가하면서 패턴과 비교하면 된다. (String[i] == pattern[j])

   j는 패턴과 테이블의 인덱스라고 보면 된다.

1. 순차적으로 비교하다 i = 3인 경우가 발생했다.

   이 때 j를 1을 감소시켜서 table[j-1] 값을 대입한다. table[j-1]을 확인하면 1인 것을 확인 할 수 있다.

   그 의미는 1번 인덱스 전까지는 접두사와 접미사가 같다는 의미이므로 패턴의 1번째 인덱스 부터 비교하면 되는 것 이다.

1. 다시 순차적으로 비교해 나가면 문자열 7번째 인덱스의 값과 다른 것을 확인 할 수 있다.

1. 다시 위의 2번과 같은 방법으로 확인하면 된다.

   j 를 1 감소시켜서 table[j-1]값을 확인하면 또 다시 1이다. 이 말뜻은 1번째 전까지는 접두사와 접미사가 같다는 것을 의미하므로 패턴의 1번째 문자열부터 비교하면 된다.

1. 그렇게 패턴의 1번째 인덱스부터 문자열의 7번째 인덱스와 다시 비교해보면 해당 패턴과 일치하는 것을 확인할 수 있다. 그렇게 되면 몇번째 인덱스에서 같은 패턴이 나왔는지 체크해두고 뒤에 또 일치하는게 있는지 확인하면 된다.
2. 찾았을 때도 처음부터 비교하는게 아니라 table의 값이 3이므로 3번째 전까지는 접두사와 접미사가 같다는 것을 의미하므로 패턴의 3번째 인덱스부터 비교해 나가면 된다.

• 패턴에서 접두사,접미사 테이블을 구하는 방법과 문자열에서 패턴을 찾는 방법을 python 코드로 확인해보자

import sys
input = sys.stdin.readline

String = input().rstrip()
pattern = input().rstrip()
table = [0] * len(pattern)

j = 0
for i in range(1, len(pattern)):
    while j > 0 and pattern[i] != pattern[j]:
        j = table[j-1]
    if pattern[i] == pattern[j]:
        j += 1
        table[i] = j

j = 0
find = []
for i in range(len(String)):
    while j > 0 and String[i] != pattern[j]:
        j = table[j - 1]
    if String[i] == pattern[j]:
        if j == len(pattern) - 1:
            find.append(i - len(pattern) + 2)
            j = table[j]
        else:
            j += 1

print(len(find)) # 문자열에서 패턴이 몇번 나오는지 출력
print(' '.join(map(str, find))) # 몇번째 인덱스에서 찾았는지 출력

Reference

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

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